Fibonacci Recursion

Need help understanding this, can someone break this down for me? I have a hard time understanding when there’s 2 functions calls adding each other.

edit: The answer is 3 but the first function call gives 1 and second function call also gives 1 which adds up to 2. I’m not sure why its 3?

function fib(n){
2	    if (n <= 2) return 1;
3	    return fib(n-1) + fib(n-2);
4	}
5	
6	fib(4)

Consider how this will be calculated:

fib(4) -> fib(4 -1) + fib(4 - 2) -> fib(3) + fib(2) -> fib(3) + 1
fib(3) -> fib(3 - 1) + fib(3 - 2) -> fib(2) + fib(1) -> 1 + 1 -> 2

fib(4) -> fib(3) + 1 -> 2 + 1 -> 3

2 Likes

If the sequence is classified as starting from 1, the fourth number in the sequence is 3, hence why it returns 3

fib 1 : 1
fib 2 : 1
fib 3 : fib 1 + fib 2 : 2
fib 4 : fib 2 + fib 3 : fib 1 + fib 1 + fib 2 : 3

1 Like