CODEWITHSUNDEEP
javascript
user2609980
user2609980

Reputation: 10484

How does return statement with assignment work for calculating Fibonacci number

To understand the below Fibonacci calculator, I wonder how the following return statement with assignment works:

let a = 0;
function foo (b) { 
  if (b === 20) return 1; 
  else return a = foo(b+1) + foo(b+1);
}

Which gives the following results:

foo(15)
>> 32
a
>> 32
foo(18)
>> 4
a
>> 4
foo(19)
>> 2
a
>> 2
foo(10)
>> 1024
a
>> 1024

What is the exact behaviour of the assignment, and why do the values of a become multiples of 2?

This can possibly also explain why this works for calculating Fibonacci:

const fib = (n, dp) => {
  dp = dp || {};
  if (dp[n]) return dp[n];
  if (n === 1) return 1;
  if (n === 0) return 0;
  return dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
};

Upvotes: 1

Views: 50

Answers (1)

Ben Aston
Ben Aston

Reputation: 55749

return a = foo(b+1) + foo(b+1) is a return statement. On the right-hand side of return here is an assignment expression (a = foo(b+1) + foo(b+1)).

The value of an assignment expression identifer = right-hand-side-expression is the result of evaluating the right-hand side expression, here: foo(b+1) + foo(b+1).

So we can now describe what is happening: foo(b+1) + foo(b+1) is evaluated first and results in a value. This value is assigned to a using the assignment operator =. The result of this expression is then also returned.

Why the code is doing this, I do not know. It might be for convenient inspection while debugging the code.

Your first function recursively calculates powers of two because the value of each recursive step is the value of the previous recursive step added to the value of itself, which is equivalent to the value of the previous recursive step multiplied by two (ie. 2n+1), with a base case value of 1 (which is 20); and the powers of two is a sequence showing how 2n varies as n is incremented one by one from zero.

A visualization of the call stack is shown below:

function foo (b = 0) { 
  if (b === 4) 
      return 1
  else 
      return foo(b+1) + foo(b+1) // 16
}
console.log(foo())

// Building the stack:

// b | return
// --------------------
// 4 | 1
// 3 | foo(4) + foo(4)
// 2 | foo(3) + foo(3)
// 1 | foo(2) + foo(2)
// 0 | foo(1) + foo(1)   <--- start here

// Unwinding the stack:

// b | return
// ---------------------
// 4 | 1                 <--- start here
// 3 | 1 + 1   
// 2 | 2 + 2
// 1 | 4 + 4
// 0 | 8 + 8 // 16

Upvotes: 2

Related Questions