Search code examples
algorithmrecursionfibonacci

Finding the number of addtion steps for a recursive program

I was going through a sample quiz and seem to have a hard time understanding 1 particular question.

  1. The Fibonacci sequence 1,1,2,3, ... can be generated iteratively by starting with the first two (0th and 1st) and generating every subsequent one by adding the previous two. Thus, if we start with the first two, the nth Fibonacci number, for n ≥ 2, can be generated by n − 1 additions. In particular, we need 6 additions to generate the 7th Fibonacci number. However, a recursive program to generate the 7th Fibonacci number needs:

(a) 20 additions (c) 5 additions (b) 13 additions (d) 18 additions

Answer: a) 20 additions

I don't quite understand how they got 20 additions. Is there a quick way to find the additions for a recursive program for a fibonacci sequence? I tried tracing through a recursive code in c that I found online but I wasn't sure what I would consider to be addition steps.

I'm just looking for an explanation of how to arrive at the answer. I would appreciate any help.

Solution

  • Make a little table with the number of additions needed for the n-th number. When you calculate the number f(x) as f(x-1) + f(x-2) you need the additions to calculate f(x-1) and the additions for f(x-2) and one more for the sum of the two numbers.

    n     additions
0     0
1     0
2     1 (= n(0) + n(1) + 1)
3     2 (= n(1) + n(2) + 1)
4     4 (= n(2) + n(3) + 1)
5     7 (= n(3) + n(4) + 1)
6    12 (= n(4) + n(5) + 1)
7    20 (= n(5) + n(6) + 1)