Recursion vs Iteration

Recursion is a very commonly used technique to express mathematical relationship as well as implement computer algorithm. Define a function recursively usually result in very concise form and ease the understanding. However, recursive function is not performance friendly in terms of stack growth and processing time.

Here is a general form of a recursive function ...

def f(n)
  if (n <= j)
    return known_value[n]
  else
    return g(f(n-1), f(n-2), ... f(n-j))

When this function is invoked, the stack size will grow linearly O(n) and the processing time will grow exponentially O(j**n)

However, the above function can be rewritten into an iteration form. The idea is to revert the order of execution, moving from the known points to the unknown values.

def f(n)
  if (n <= j)
    return known_value[n]
  for i in 0..j
    cache[i] = known_value[i]
  for i in (j+1) .. n
    cache[i] = g(cache[i-1], cache[i-2], ... cache[i-j])
  return cache[n]

In this iteration form, the stack size will not grow and the processing time will grow linearly O(n). Therefore, performance gains significantly when the recursive form is rewrittened in the iteration form.