find nth value in fib sequence javascript using previously declared variables

Question

I'm trying to find the nth value of the fib sequence in javascript, but I got stuck with another problem prior to that and I'm trying to understand why.

function nthFib(n) {
  var fib = [0, 1];
  var l = fib[fib.length-1];
  var s = fib[fib.length-2];  

  while(fib.length < n) {
    fib.push(fib[fib.length-1] + fib[fib.length-2]);
  }

  console.log(fib); 

}

nthFib(5);

Right now when I console log I'm getting what I want which is the array building up: [0, 1, 1, 2, 3]

BUT if I do this in the while loop instead to have cleaner code:

while(fib.length < n) {
  fib.push(s + l);
}

I guess my while loop doesn't have access to those variables and in turn I get this result: [0, 1, 1, 1, 1]

WHY?

Answer 1

You have to modify s, l inside the while loop. Take a look at this code.

function nthFib(n) {
  var fib = [0, 1];


  while(fib.length < n) {

      var l = fib[fib.length-1];
      var s = fib[fib.length-2];  
      fib.push(s + l);

  }

  console.log(fib); 

}

nthFib(5);

Answer 2

I think this is a much better function as it uses a linear iterative process with proper tail recursion

function fib(n) {
  function iter(xs, i, a, b) {
    if (i === 0) return xs;
    return iter(xs.concat(b), i-1, b, a+b);
  }
  return iter([0], n, 0, 1);
}

Examples

fib(0);
//=> [ 0 ]
fib(1);
//=> [ 0, 1 ]
fib(2);
//=> [ 0, 1, 1 ]
fib(3);
//=> [ 0, 1, 1, 2 ]
fib(4);
//=> [ 0, 1, 1, 2, 3 ]
fib(5);
//=> [ 0, 1, 1, 2, 3, 5 ]
fib(6);
//=> [ 0, 1, 1, 2, 3, 5, 8 ]
fib(10);
//=> [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]

Explanation

The iter function takes 4 state variables

• xs - the fib series, initalized with [ 0 ]
• i - the decrementing iterator used to terminate the recursion, initialized with n
• a - the first fib number, initialized with 0
• b - the second fib number, initialized with 1

The way this works is, once i has reached 0, xs will be returned.

Let's see how fib(5) is computed

//   xs             i  a  b
// -----------------------------
iter([0],           5, 0, 1);
iter([0,1],         4, 1, 1);
iter([0,1,1],       3, 1, 2);
iter([0,1,1,2],     2, 2, 3);
iter([0,1,1,2,3],   1, 3, 5);
iter([0,1,1,2,3,5], 0, 5, 8);
// -----------------------------
//=> [0,1,1,2,3,5]

---

ES6

Using a U-combinator with ES6, you can get a pretty slimmed down version of the same function

// ES6
let fib = n => (
  f => f(f, [0], n, 0, 1)
)(
  (f, xs, i, a, b) => i === 0 ? xs : f(f, xs.concat(b), i-1, b, a+b)
);

fib(10);
//=> [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]

Cool !