How to improve my Fibonacci solution?

1

My solution (pasted below) feels rather crude. I think I know what a better way would involve, but can’t wrap my mind around it to actually create it. Analysis:

  • This is not a job for a simple for() loop.
  • There is no need to build an array of the Fibonacci sequence. It is unnecessary, and would consume lots of memory for large values of num.
  • What we want is a function that will simply return the next Fibonacci number. This means the function must maintain its state between invocations. (please see the edit at bottom)

Put together, it looks like a job for a generator function (with a “yield” rather than “return”). JS apparently has those now, but even with the MDN docs, I still can’t figure out how to write one.

My code is below. It it indeed a poor man’s generator function, but the ugly thing about it is the need to maintain state in two global vars, which must be reinitialized each time. A generator function would hide all these details inside.

var iterCount = 0;
var prevTwo = [0, 0]; // maintain last 2 Fibonacci numbers

function nextFib() {
  iterCount++;
  if ( iterCount === 1) {
    prevTwo[1] = 1;
    return 1;
  }
  var result = prevTwo[0] + prevTwo[1];
  // update the state array:
  prevTwo[0] = prevTwo[1];
  prevTwo[1] = result; 
  return result;
}

function sumFibs(num) {
  var result = 0;
  
  // must reset for each testcase
  iterCount = 0; 
  prevTwo = [0, 0];
  
  fib = nextFib();
  while ( fib <= num ) {
    if ( fib % 2 !== 0) { // is it odd?
      result += fib;
    }
    fib = nextFib();
  }  
  
  return result;
}

sumFibs(4);

On edit: The instruction reads:

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

So we’re not merely computing n-th Fib number - a for or a while loop would work fine for that. We have to actually see all the “intermediate” numbers in a sequence. (Also, we don’t even know what the n is, sow e have to keep computing Fib() until the result is >= num.)

2

Note that I’m using fibonacci series that starts with 1

1, 1, 2, 3, 5...

1 It can be a job for simple loop.

// n > 0
function fib(n) {
  if (n <= 2)
    return 1;
  
  var a = b = 1;
  while (--n > 1) {
    a = b;
    b = a+b;
  }
  
  return b;
}

2 Array that stores previous computations is unnecessary but not for the reason of high memory consumption. If you compute 100 fib numbers and store all previous computations, the result is only array holding 100 numbers–that occupies some memory but not ‘lots’ not even when it’s holding 1000.

3 If somehow that’s your major concern, using generator might make sense.

For clarity, I like the recursion one.

function fib(n) {
    if (n <= 2) return 1;
    return fib(n-2) + fib(n-1)
}

I haven’t used generator a lot, so I have to do some work to improve the clarity of your version. But, apparently, yours look rather complicated to me.
I’m probably too tired to get this straight but why are you doing this test?

fib % 2 !== 0

Is it like saying if fib is odd, then add to the result?

3

The oddness test is part of the requirement: “return the sum of all odd Fibonacci numbers”. (Which IMO unnecessarily complicates the task, while a simple “is num odd” challenge is included earlier).

Yes, the loop or the recursion can work too. The reason I don’t like to use them in this case is that you’re not just looking for the n-th Fib number. To fulfill the task, as I understand it, you have to look at all the numbers in the sequence (and add them, if they happen to be odd). So these functions would have to be called n times, each time computing the whole sequence starting from 1, again and again. In other words, it’s like counting to five by doing
1
12
123
1234
12345
…instead of just once. It doesn’t seem efficient.

4

@marekjedlinski I can give you a hint that only every third Fibonacci number will be even. It’s actually provable but you can see it by listing the sequence.

@gunhoo93 Keep in mind that recursive solution while looking clear will be a very intensive from a computational standpoint. It’s better to either use linear generation (as in opening post) or a tail call. The recursive solution is O(2^n), linear generator is O(n) and so is tail-call in our case. Big Oh notation is a way to describe the time complexity of a running algorithm.

5

  1. Oh, I see it’s the requirement. The name of the function was sumFibs and I wasn’t really expecting it.

  2. Well I would pick code clarity and conciseness over small performance benefit. But even what you addressed can be resolved into a simple loop. (I’ve made little tweak to definition of fib series)

// using fib_series 0, 1, 1, 2, 3...
// sumFib(0) = 0
// sumFib(1) = 1
// sumFib(2) = 2...
function sumFib(n) {
  if (n <= 1)
    return n;

  var sum = 0;
  for (var a=b=1; --n > 0; a=b, b=a+b) {
    sum += a;
  }

  return sum;
}
6

Yea I do always keep that in mind.

7

OK, so I figured out the generator function. This is my new solution:

function* fibMaker( max ) {
  yield 1;      
  var cur = 1, prev = 0, val=0;  
  while ( prev+cur <= max ) {    
    val = prev+cur;
    prev = cur;
    cur = val;    
    yield val;       
  }}

function sumFibs(num) {
  var result = 0;
  var fib = fibMaker( num );
  var r;
 
  r = fib.next();   
  while ( ! r.done  )  {    
    if ( r.value % 2 !== 0) { // use only odd values
      result += r.value;
    }
    r = fib.next();
  }  
  
  return result;
}

sumFibs(4);

And here is a generalized fibonacci function (returns n first fib numbers):