Sum All Odd Fibonacci Numbers Part 2

Question

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);

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, May 16 '20 at 13:25
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, May 16 '20 at 13:29
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, May 16 '20 at 13:35
https://stackoverflow.com/questions/6037472/can-a-fibonacci-function-be-written-to-execute-in-o1-time Fibonacci with O(1) time and space, just for reference. — M. Mennan Kara, May 16 '20 at 18:13

score 2 · Accepted Answer · answered May 16 '20 at 13:40

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

I'm glad you figured it out! – Pointy May 16 '20 at 13:41

score 1 · Answer 2 · answered May 16 '20 at 18:08

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));

Sum All Odd Fibonacci Numbers Part 2

2 Answers2