how does this Fibonacci solution work in JavaScript?

Question

Would really appreciate an explanation on the given solution below. How does JavaScript 'store' the s variable as an array as I would think it continually would get overwritten as the s.push(s[s.length - 1] + s[s.length - 2]); line doesn't get hit until after the recursion?

From my understanding JavaScript reads left to write then up to down, so it will never hit the push line until after it has gone through all cycles of s?

How its storing it an array?

function fibonacci(n) {
  if (n === 1) {
    return [0, 1];
  } else {
    var s = fibonacci(n - 1);
    s.push(s[s.length - 1] + s[s.length - 2]);
    return s;
  }
}
console.log(fibonacci(8));

The inner most method return an array i.e. [0, 1] so in simple term s is an array — Satpal
– Satpal, Commented May 12, 2017 at 12:08

Alexander · Accepted Answer · 2017-05-12 12:23:54Z

1

When your start the script with n=8 the variable s will be created:

var s = fibonacci(n - 1);

The function will be recurcively called until n becomes equal to 1. In this step function returns array with two elemens:

 return [0, 1];

This array is returned to s. In next steps the array length will be increased by push() method:

s.push(s[s.length - 1] + s[s.length - 2]);

So, the function step by step exits from recursion.

edited May 12, 2017 at 12:23

answered May 12, 2017 at 12:18

Alexander

4,5527 gold badges31 silver badges46 bronze badges

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

Comments

Pointy · Accepted Answer · 2017-05-12 12:32:29Z

let me explain you the execution of code, at the first time, you call fibonacci(8)

//8>1 so it will go to the else part
    var s = fibonacci(n - 1); // again it will call fibonacci(7)
    s.push(s[s.length - 1] + s[s.length - 2]);
    // here s is [0,1,1,2,3,5,8,13] so s.push(s[8-1]+s[8-2])) is [0,1,1,2,3,5,8,13,21]
    return s; //here s is [0,1,1,2,3,5,8,13,21]

//7>1 so it will go to the else part
    var s = fibonacci(n - 1); // again it will call fibonacci(6)
    s.push(s[s.length - 1] + s[s.length - 2]);
   // here s is [0,1,1,2,3,5,8] so s.push(s[7-1]+s[7-2])) is [0,1,1,2,3,5,8,13]
    return s; //here s is [0,1,1,2,3,5,8,13]
.
.
.
.

//2>1 so it will go to the else part
    var s = fibonacci(n - 1); // again it will call fibonacci(1)
    s.push(s[s.length - 1] + s[s.length - 2]);
    // here s is [0,1] so s.push(s[2-1]+s[2-2])) is [0,1,1]
    return s; //here s is [0,1,1]


//1 is not > 1 so it will go to the if part 
    return [0, 1]; // again it will call fibonacci(0)

Pointy · Accepted Answer · 2017-05-12 12:44:28Z

0

The code code be written as a simple iteration, which might make it more clear:

function fibonacci(n) {
  var s = [0, 1];
  while (n > 1) {
    s.push(s[s.length - 1] + s[s.length - 2]);
    n -= 1;
  }
  return s;
}

In this case, the recursive version isn't much of an improvement, in my opinion.

answered May 12, 2017 at 12:44

community wiki

Pointy

Collectives™ on Stack Overflow

how does this Fibonacci solution work in JavaScript?

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related