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