How does the fibonacci recursive function "work"?
RecursionFibonacciRecursion Problem Overview
I'm new to Javascript and was reading up on it, when I came to a chapter that described function recursion. It used an example function to find the nth number of the Fibonacci sequence. The code is as follows:
function fibonacci(n) {
if (n < 2){
return 1;
}else{
return fibonacci(n-2) + fibonacci(n-1);
}
}
console.log(fibonacci(7));
//Returns 21
I'm having trouble grasping exactly what this function is doing. Can someone explain what's going on here? I'm getting stuck on the 5th line, where the function calls itself. What's happening here?
Recursion Solutions
Solution 1 - Recursion
You're defining a function in terms of itself. In general, fibonnaci(n) = fibonnaci(n - 2) + fibonnaci(n - 1). We're just representing this relationship in code. So, for fibonnaci(7) we can observe:
fibonacci(7)is equal tofibonacci(6)+fibonacci(5)fibonacci(6)is equal tofibonacci(5)+fibonacci(4)fibonacci(5)is equal tofibonacci(4)+fibonacci(3)fibonacci(4)is equal tofibonacci(3)+fibonacci(2)fibonacci(3)is equal tofibonacci(2)+fibonacci(1)fibonacci(2)is equal tofibonacci(1)+fibonacci(0)fibonacci(1)is equal to 1fibonacci(0)is equal to 1
We now have all the parts needed to evaluate fibonacci(7), which was our original goal. Notice that the base case -- return 1 when n < 2 -- is what makes this possible. This is what stops the recursion, so that we can can start the process of unrolling the stack and summing the values we're returning at each step. Without this step, we'd continue calling fibonacci on smaller and smaller values right up until the program finally crashed.
It might help to add some logging statements that illustrate this:
function fibonacci(n, c) {
var indent = "";
for (var i = 0; i < c; i++) {
indent += " ";
}
console.log(indent + "fibonacci(" + n + ")");
if (n < 2) {
return 1;
} else {
return fibonacci(n - 2, c + 4) + fibonacci(n - 1, c + 4);
}
}
console.log(fibonacci(7, 0));
Output:
fibonacci(7)
fibonacci(5)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(6)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(5)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
Values at the same level of indentation are summed to produce the result for the previous level of indentation.
Solution 2 - Recursion
There are many good answers here, but I made this diagram which helps better explain the outcome of the function. The only values that will ever be returned are 1 or 0 (your example returns 1 for n < 2, but should instead return n).
This means that each recursive call will eventually wind up returning either a 0 or 1. Those end up being "cached" in the stack and "carried up" into the original invocation and added together.
So if you were to draw this same diagram out for each value of 'n' you could manually find the answer.
This diagram roughly illustrates how every function is returned for fib(5).
This shows the control flow, i.e. the order of execution for the functions. Remember code is always executed left->right and top-> bottom. So whenever a new function is called it is paused and then the next invocation occurs.
The following illustrates the actual control flow based on your original post. Please note the base condition is if (n <= 0) {return 0} else if (n <= 2) {return 1;} for simplification:
1. fib(5) {
return fib(4) + fib(3);
2. fib(4) {
return fib(3) + fib(2);
3. fib(3) {
return fib(2) + fib(1);
4. fib(2) {
A= return 1;
};
5. fib(1) {
B= return 1;
};
C= return 2; // (1 + 1)
};
6. fib(2) {
D= return 1;
};
E= return 3; // (2 + 1)
};
7. fib(3) {
return fib(2) + fib(1);
8. fib(2) {
F= return 1;
};
9. fib(1) {
G= return 1;
};
H= return 2; // (1 + 1)
};
I= return 5; // (3 + 2)
};
Solution 3 - Recursion
Step 1) When fibonacci(7) is called imagine the following (notice how I changed all the n's to 7):
function fibonacci(7) {
if (7 < 2){
return 1;
}else{
return fibonacci(7-2) + fibonacci(7-1);
}
}
Step 2) Since (7 < 2) is obviously false, we go to fibonacci(7-2) + fibonacci(7-1); which translates to fibonacci(5) + fibonacci(6); Since fibonacci(5) comes first, that get called (changes the n's to 5 this time):
function fibonacci(5) {
if (5 < 2){
return 1;
}else{
return fibonacci(5-2) + fibonacci(5-1);
}
}
Step 3) And or course fibonacci(6) also gets called, so what happened is for everyone call of fibonacci 2 new fibonacci get called.
Visualization:
fibonacci(7)
____|_____
| |
fibonacci(5) fibonacci(6)
____|____ ____|_____
| | | |
fib(3) fib(4) fib(4) fib(5)
See how it branches? When is it going to stop? When n becomes less than 2, thats why you have if (n < 2). At that point the branching stops and everything gets added together.
Solution 4 - Recursion
Hopefully the following helps. Calling:
fibonacci(3)
will get to line 5 and do:
return fibonacci(1) + fibonacci(2);
the first expression calls the function again and returns 1 (since n < 2).
The second calls the function again, gets to the 5th line and does:.
return fibonacci(0) + fibonacci(1);
both expressions return 1 (since n < 2 for both), so this call to the function returns 2.
So the answer is 1 + 2, which is 3.
Solution 5 - Recursion
These two functions gave me a much clearer explanation of recursion (from this blog post):
function fibDriver(n) {
return n === 0 ? 0 : fib(0, 1, n);
}
function fib(a, b, n) {
return n === 1 ? b : fib(b, a + b, n-1);
}
// Get the 10th fibbonacci number (when excluding the 0)
console.log(fibDriver(10))
Solution 6 - Recursion
To calculate nth fibonacci number, the relation is F(n) = F(n-2) + F(n-1).
If we implement the relation in the code, for nth number, we calculate the (n-2)th and (n-1)th number using the same method.
Each subsequent number is the sum of the previous two numbers. Thus, the seventh number is the sum of the sixth and fifth numbers. More generally, the nth number is the sum of n - 2 and n - 1, as long as n > 2. As recursive functions need a stop condition to stop recursing, here n<2 is the condition.
f(7) = F(6) + F(5);
in turn, F(6) = F(5) + F(4)
F(5) = F(4) + F(3)...
it goes on until n<2
F(1) returns 1
Solution 7 - Recursion
/*
- Steps Fibonacci recursion
-
- 3 gets passed. (3 is printed to the screen during this call)
-
- Fibonacci A gets decrements by 2 and recursion happens passing 1 as a param. (1 is printed to the screen during this call)
-
- Fibonacci A hits the base case returning 1 and it "unwinds". (No recursion here)
-
- Fibonacci B gets called, decrementing the previous value of n (3 was the previous value of n before A made the returning call) to 2. (2 is printed to the screen during this call)
-
- Fibonacci A is called again subtracting 2 from n (2-2=0) and passes 0 as a param. (1 is printed to the screen during this call since it's converted from 0)
-
- Fibonacci A hits the base case and "unwinds" (no recursion here)
-
- Fibonacci B is called subtracting 1 from 2 (2 was the previous value of n before A made the returning call) and passes 1 as a param. (1 is printed to the screen during this call)
-
- Fibonacci B now hits the base case, returning 1 and "unwinds" (no recursion here)
-
- Fibonacci B retraces it's steps back through All previous fucntion calls and values of n (n=2 in our case) and adds [them] to the copy of n=1 stored in its local scope
-
- Once Fibonacci B completes the "unwinding" process, it returns the calculated value to the original caller (no recursion here)
Note* Each instance of Fibonacci recursion creates its own scope and stores the returned value in a copy of n (in our case 1). As it the function "unwinds" it executes subsequent code that receive the value of n at that time. (all functions that call other functions "unwind" back through previous calls once they return)
In the last call of our Fibonacci example, Fibonacci B receives the value of n=2 as Fibonaccci A "unwinds" since that was the last value before it made the returning call.
Once Fibonacci B reached the base case and "unwound", it retraced its steps back through all previous values of n (in our case just n=2) and added [them] to its local copy of n=1.
-
The result when passing the number 3 is: 3 1 2 1 1 (3) */
var div = document.getElementById('fib');
function fib( n, c ) { var indent = ""; for (var i = 0; i < c; i++) { indent += " "; } var v = n===0 ? 1 : n var el = document.createElement('div'), text = indent + "fibonacci(" + v + ")"; el.innerHTML = text; div.appendChild(el); if(n<2){ return 1; } return fib(n-2, c + 4) + fib(n-1, c + 4); }
Solution 8 - Recursion
The function is calling itself. That's simply the definition of a recursive function. In the 5th line it is transferring execution to itself by passing parameters that will result in a value.
To ensure that a recursive function doesn't turn into an endless loop, there must be some sort of condition that doesn't call itself. The goal of your code in the question is to perform the calculations of a fibonacci sequence.
Solution 9 - Recursion
Fibonacci algorithm with recursive function based on ES6
const fibonacci = ( n, k = 1, fib2 = 0, fib1 = 1 ) => {
return k === n ?
(() => { return fib1; })()
:
(() => {
k++;
return fibonacci(n, k, fib1, fib1 + fib2);
})();
}
console.info(' fibonacci ' + 11 + ' = ' + fibonacci(11));
Solution 10 - Recursion
look, fib is
> t(n) = t(n - 1) + n; > > if n = 0 then 1
so let see how recursion works, I just replace n in t(n) with n-1 and so on. it looks:
> t(n-1) = t(n - 2) + n+1; > > t(n-1) = t(n - 3) + n+1 + n; > > t(n-1) = t(n - 4) + n+1 + n+2 + n; > >. > >. > >. > > t(n) = t(n-k)+ ... + (n-k-3) + (n-k-2)+ (n-k-1)+ n ;
we know if t(0)=(n-k) equals to 1 then n-k=0 so n=k we replace k with n:
> t(n) = t(n-n)+ ... + (n-n+3) + (n-n+2)+ (n-n+1)+ n ;
if we omit n-n then:
> t(n)= t(0)+ ... + 3+2+1+(n-1)+n;
so 3+2+1+(n-1)+n is natural number. it calculates as Σ3+2+1+(n-1)+n = n(n+1)/2 => n²+n/2
the result for fib is : O(1 + n²) = O(n²)
This the best way to understand recursive relation
Solution 11 - Recursion
Sharing a simpler code for fib in JS/ES6 using recursion.
function fib(n, first = 1, second = 1) {
if (n <= 2) return 1;
[first, second] = [second, first + second];
return (n - 2 === 1) ? second : fib(n - 1, first, second);
}
console.log(fib(10));
Solution 12 - Recursion
It is going to cascase like this:
> 7 - 2 = 5 --> fibonacci(5)
> 7 - 1 = 6 --> fibonacci(6)
Like given in the implement the left hand side will always decrease by
2 and
the right hand decrease by 1, so it will casecase this way until it hits 1, once it hits 1 it will add it up to the outputs of the right hand function 1 + fibonacci(n-1);, which as well will always stop at 1's as per the implementation:
if (n < 2){
return 1;
}
Eventually they all end up having 1's in memory and start adding them up from left to right... consider the cascading representation below, adding up all 1's at the bottom will make it 21.
if n > 2______________Left always n - 2 __________&____________Right always n - 1 ________else n = 1
7
5 6
3 4 4 5
1 2 2 3 2 3 3 4
1 1 1 1 1 1 2 1 1 1 2 1 2 2 3
1 1 1 1 1 1 1 1 1 2
1 1
1+ 1+1+ 1+1 1+ 1+1+ 1+1+ 1+1+1+ 1+1+1+ 1+1+ 1+1+1 = 21
7th position in Fibonacci sequence is 21, we can test it with array:
const fibArray = [1, 1, 2, 3, 5, 8, 13, 21]
console.log(fibArray[7]) //-> 21