Recursion

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:
- f₁ = 1
- f₂ = 1
- f_n = f_n_-1 + f_n_-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);
}