Textbook

CS 3343/3341  Analysis of Algorithms  Fall 2012  Recitation 2  In-Class Problems     Week 2: Sep 4-6

Look at the page Recursive Calculation of Fibonacci Numbers. Consider the excessive execution time taken in calculating Fibonacci numbers using recursion.

1. Let A[n] be the number of calls needed to calculate F[n] recursively (including the initial call). This problem investigates the numbers A[n], for n >= 0.
   1. By hand calculate the numbers A[n] for 0 <= n <= 10..
      [You can do this by drawing pictures of the tree of function calls including the initial call, and just counting the calls by hand. Here are pictures of these trees for n = 0, 1, 2, 3, 4:

      // the recursive function f // returns the nth Fibonacci number, n >= 0 int f(int n) { if (n <= 1) return n; return f(n-1) + f(n-2); } // Trees of function calls in calculating f(0),f(1),f(2),f(3). A[0]: f(0), A[1]: f(1), A[2]: f(2) A[3]: f(3) / \ / \ f(0) f(1) f(1) f(2) / \ f(0) f(1) A[4]: f(4) / \ f(2) f(3) / \ / \ f(0) f(1) f(1) f(2) / \ f(0) f(1)

      Thus A[1] = 1, A[2] = 3, etc.

   2. Stare at the 11 numbers, and at the trees of function calls, including trees for n > 4. Can you come up with a recurrence equation that the numbers A[n] satisfy? [A recurrence equation would be of the form A[n] = some formula involving one or more A[i] for i < n.]

   3. Prove that your formula in part ii above is true.

   4. Whether you make headway on parts ii and iii above, separately list the values of A[n] and the Fibonacci numbers F[n+1] side-by-side in the table below:

      n	A[n]	F[n+1]
      0	1	1
      1	1	1
      2	3	2
      3		3
      4
      5
      6
      7
      8
      9
      10
      11

      Does any formula for A[n] involving F[n+1] come to mind?

   5. Use induction to prove that the formula you guessed in part iv for A[n] in terms of F[n+1] is true for all n >= 0.