previous | start | next

## The Efficiency of Recursion

- Although recursion can be a powerful tool to implement complex algorithms, it can lead to algorithms that perform poorly.
- We will analyze the question of when recursion is beneficial and when it is inefficient.
- For our study we will examine the Fibonacci sequence of numbers defined by the equations:
  - f1 = 1
  - f2 = 1
  - fn = fn-1 + fn-2
- The first ten terms of the Fibonacci sequence are

  > 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

- One can easily write a recursive function to compute Fibonacci numbers.

  >     int fib(int n)
  >     {
  >        if (n <= 2) return 1;
  >        else return fib(n - 1) + fib(n - 2);
  >     }

previous | start | next