previous | start | next

---

The Efficiency of Recursion

• The function above works correctly, but for moderately large values of n it takes an amazing long time to compute the value.
• Try running a test program with n between 30 and 50 to see this effect.
• To determine the problem, we insert trace messages into the function.

  int fib(int n)
  {
     cout << "Entering fib: n = " << n << "\n";
     int f;
     if (n <= 2) f = 1;
     else f = fib(n - 1) + fib(n - 2);
     cout << "Exiting fib: n = " << n
        << " return value = " << f << "\n";
     return f;
  }
  

---

previous | start | next