Recursive calls for fibonacci sequence

Question

For finding Fibonacci numbers recursively the relation is f(n)=f(n-1)+f(n-2). How many times is f(n-i) called (in terms of n and i) for recursive function of f(n) ?

I understand that while tracing the recursive calls a binary tree is made. However there does not appear to be any fixed pattern for determining number of recursive calls to f(n-i).Any advice ?

For example, in finding f(5),

f(5)=f(4)+f(3)  
f(5)=f(3)+f(2)+f(2)+f(1)  
f(5)=f(2)+f(1)+f(1)+f(0)+f(1)+f(0)+f(1)  
f(5)=f(1)+f(0)+f(1)+f(1)+f(0)+f(1)+f(0)+f(1)

Here number of calls to f(5)-1,f(4)-1,f(3)-2,f(2)-3,f(1)-5,f(0)-3.

Thanks.

Answer 1

The sequence 1, 1, 2, 3, 5, 3 should look familiar, because ignoring the last number it is the Fibonacci sequence again.

Let c(x) be the number of times fib(x) is called in the computation of fib(n).

• c(x) = 0 for all x > n, since fib(x) is never called.
• c(n) = 1, as fib(n) is called exactly once.
• c(x) = c(x + 1) + c(x + 2) for all 0 < x < n, as fib(x) is called from fib(x + 1) and fib(x + 2).
• c(0) = c(2), a special case, since fib(0) is called from fib(2) but not fib(1).

So the sequence c(n), c(n-1), ..., c(2), c(1) is the Fibonacci sequence and c(0) is equal to c(2).

In terms of i and n,

• fib(n - i) is called fib(i + 1) times for 0 ≤ i < n
• fib(n - n) = fib(0) is called fib(n - 1) times.