CODEWITHSUNDEEP
javascriptfunctionrecursion
Nix Siow
Nix Siow

Reputation: 21

Javascript function. Don't understand how function inside self-function work

would like to ask about a JavaScript function.

I don't understand below function, I thought at line 4 fib(n-1) will return 1 and the latter fib(n-2) will return 0, and then they both add together as 1.

May I know why the final result for f(10); will be 55, can't get my head around this.

Anyone can help to explain to me what happening behind the scene, please?

Thanks! ;)

var f = function fib(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    if (n > 1) return fib(n - 1) + fib(n - 2);      // *2
};
f(10);       // 55

ref: https://slides.com/concise/js/fullscreen#/35

Upvotes: 2

Views: 57

Answers (2)

JLRishe
JLRishe

Reputation: 101662

Like this. This is a typical recursive function, with two base cases and one recursive step.

Remember that if n is 10, then fib(n - 1) is fib(9), and so on:

fib(10) = fib(9) + fib(8) = 34 + 21 = 55
fib(9)  = fib(8) + fib(7) = 21 + 13 = 34
fib(8)  = fib(7) + fib(6) = 13 +  8 = 21
fib(7)  = fib(6) + fib(5) =  8 +  5 = 13
fib(6)  = fib(5) + fib(4) =  5 +  3 =  8
fib(5)  = fib(4) + fib(3) =  3 +  2 =  5
fib(4)  = fib(3) + fib(2) =  2 +  1 =  3
fib(3)  = fib(2) + fib(1) =  1 +  1 =  2
fib(2)  = fib(1) + fib(0) =  1 +  0 =  1
fib(1)  =                              1
fib(0)  =                              0

Side note: Although your example is a good illustration of recursive functions, it's an extremely inefficient way to calculate fibonacci numbers. A much better approach is to use memoization to eliminate the bulk of the inefficiency:

var fib = (function () {
  var cache = [0, 1];
  
  return function fib(num) {
    if (!(num in cache)) { 
        cache[num] = fib(num - 1) + fib(num - 2);
    }
    return cache[num];
  };
})();

console.log(fib(10));

http://jsperf.com/fibonacci-memoization-2015-04-01

Upvotes: 8

David Haim
David Haim

Reputation: 26476

this is called "recursive function" which one function calls itself.

basically there is no restriction (in terms of the OS) of doing so, a function basically gets interpreted/compiled to assembly code , and this assembly code can be copied and re-run with different (or the same) arguments.

Upvotes: 0

Related Questions