1

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.

Shv
  • 43
  • 8
  • See [Number of calls for nth Fibonacci number](http://stackoverflow.com/questions/1738923/number-of-calls-for-nth-fibonacci-number) – tom Jan 15 '14 at 10:44
  • Thanks but that discussion is on the total number of calls made to for finding f(n). However, I want to know about the calls made to one specific f(n-i) in computation of f(n). – Shv Jan 15 '14 at 11:08

1 Answers1

0

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.
tom
  • 21,844
  • 6
  • 43
  • 36