Sum All Odd Fibonacci Numbers Part 2

4
votes

My Question

Given a positive integer num, return the sum of all odd Fibonacci numbers that are less than or equal to num.

The first two numbers in the Fibonacci sequence are 1 and 1. Every additional number in the sequence is the sum of the two previous numbers. The first six numbers of the Fibonacci sequence are 1, 1, 2, 3, 5 and 8.

For example, sumFibs(10) should return 10 because all odd Fibonacci numbers less than or equal to 10 are 1, 1, 3, and 5.

My Answer

function sumFibs(num, total = [1, 1]) {

  const n = total[total.length - 1] + total[total.length - 2];

  if(n > num){

    return total;

  }

  if(n %2 ==0){
    total.push(n);
  }

 return sumFibs(num, total);

}

sumFibs(4);

The Problem

It keeps saying maximum call stack exceeded. I am pretty sure it is because of the second if statement. Any idea how I can fix this?

I even tried this: 

function sumFibs(num, total = [1, 1]) {

  const n = total[total.length - 1] + total[total.length - 2];

  if(n > num){

    return total;

  }




let x = Array.from(n);
let y = x.filter((item)=>{
  return item % 2== 0
})
total.push(...y)


 return sumFibs(num, total);

}

sumFibs(4);
2
javascriptalgorithmrecursion
the total.push() doesn't work? - AndrewNeedsHelp
It does, sorry I missed it. But you have to compute all the Fibonacci numbers, not just the odd ones. The sum is of just the odd ones. - Pointy
interesting point! Which makes summing all of the odd numbers even harder. Perhaps this is most easily achieved by a reduce and a filter outside of the recursive function (if total can be taken from the function) hmmm - AndrewNeedsHelp
function sumFibs(num, total = [1, 1]) { const n = total[total.length - 1] + total[total.length - 2]; if(n > num){ let answer = total.filter((item)=>{ return item % 2 == 0; }).reduce((totalII, filteredItems)=>{ return totalII + filteredItems }, 0) return answer } total.push(n) return sumFibs(num, total); } sumFibs(4); (FEELS ALMOST THERE!) - AndrewNeedsHelp
stackoverflow.com/questions/6037472/… Fibonacci with O(1) time and space, just for reference. - M. Mennan Kara

2 Answers

2
votes

I finally got there, so to explain:

I was not adding the even Fibonacci numbers to the array, as pointed out by Pointy. This was making the array incorrect.

This needed to move to the end. Once all of the Fibonacci calculations had been made. Then I could filter and reduce the break out clause of the recursive function: 

function sumFibs(num, total = [1, 1]) {

  const n = total[total.length - 1] + total[total.length - 2];

  if(n > num){

  let answer = total.filter((item)=>{
    return item % 2 != 0;
  }).reduce((totalII, filteredItems)=>{
    return totalII + filteredItems
  }, 0)

  return answer



  }

total.push(n)

 return sumFibs(num, total);

}

console.log(sumFibs(4));

console.log(sumFibs(75204));
1
votes

For contrast, here's an iterative, O(1) space, alternative:

function f(n){
  if (n < 1)
    return 0;
    
  let result = 1;
  let a = 1
  let b = 1
  
  while (b <= n){
    if (b & 1)
      result += b;
    [a, b] = [b, a + b]
  }
  
  return result;
}

console.log(f(10));
console.log(f(4));
console.log(f(75204));