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?

If you're storing the whole sequence history it may consume a lot of memory for large n — Paul S.
– Paul S., Commented Jun 22, 2015 at 1:34

Mulan · Accepted Answer · 2015-06-22 01:49:12Z

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 !

edited Jun 22, 2015 at 1:49

answered Jun 22, 2015 at 1:21

Mulan

136k35 gold badges240 silver badges276 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

guest271314 Over a year ago

fib() called without parameter appear to return RangeError: Maximum call stack size exceeded

Mulan Over a year ago

@guest271314 that's correct. fib requires a number input.

Fawzan · Accepted Answer · 2015-06-22 01:14:06Z

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

answered Jun 22, 2015 at 1:14

Fawzan

4,8508 gold badges43 silver badges87 bronze badges

4 Comments

Stack Overflow Over a year ago

ok but why? Is it because as long as the condition in the while loop holds true it doesn't have access to those previous variables? If that's the case how does it still know what fib is?

Fawzan Over a year ago

it is because, each time you try find the fib value, you need the last two fib values you found. When the while loop runs, it only modifies the code which has in its own block. It does not jump back and edit the previous code. So you must have the l, s inside the while loops block itself. clear?

Stack Overflow Over a year ago

Yes! So it only has access to fib, not to l & s, right?

Fawzan Over a year ago

It can access l & s. But you have to actually access it and modify it. It won't automatically modify the values. clear?

Collectives™ on Stack Overflow

find nth value in fib sequence javascript using previously declared variables

2 Answers 2

2 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related