Recursion and Iteration

Recursion

The Fibonacci sequence is defined as follows:

fib(n) = { 0 if n == 0
         { 1 if n == 1
         { otherwise, fib(n-1) + fib(n-2)
 
This definition is recursive, since the definition of "fib" depends on itself.  This recursive definition indicates the following simple recursive implementation:

function fib(n)

  if n == 0 then
    return 0
  end

  if n == 1 then
    return 1
  end

  return fib(n-1) + fib(n-2)
end

This function is recursive because it calls itself.

This naive implementation has several problems though:
  1. Because it is recursive, you are limited by the stack size.  You will not be able to compute fib(n) for very large n, since you will run out of stack.
  2. The function duplicates a lot of work.  For e.g., fib(5) depends on fib(3), but fib(4) also depends on fib(3).  In the above implementation, fib(3) is computed again each time it is needed.  Instead, a better approach would be to cache the results of each calculation and re-use them when needed.
  3. The runtime complexity of the algorithm is exponential, approx. O(2^n), which is abysmal.

Iteration

You can define the Fibonacci sequence in terms of a recurrence relation:

fib(n) = fib(n-1) + fib(n-2)

Notice that fib(n) depends on two values: the previous two numbers in the sequence.  What if we stored these last two numbers when calculating the next number?  Let's call the previous two numbers a and b.  At each iteration i, the next number c is just a + b:

c(i) = a(i) + b(i)

Once we compute the next number, we must update our old a and b:

a(i+1) = b(i)
b(i+1) = c(i)

This indicates the following iterative implementation:

function fib(n)

  local a = 0
  local b = 1
  local c = 1

  for i = 1, n do
    c = a + b
    a = b
    b = c
  end

  return c
end

Notice that we have removed the recursion from this implementation.  The new fib does not depend on itself.  Instead, the function is implemented as a for-loop which computes the next number in the sequence based on the previous two numbers.

The implementation is very efficient, because we only store the values we need for the next iteration (a, b, and c).

Comments