Friday, January 25, 2008

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]
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.

1 comment:

Krzysztof (Christopher) Kliƛ said...

This is very true for OO languages. Functional language interpreters/compilers usually support tail call optimization, which does not eat up the stack. Unfortunately, as far as I know, TCO is not scheduled to be implemented natively in JVM, so FLs running on Java need to do some tricks to work around this problem - and they mostly do it by turning recursive calls into iterations.
Great post by the way, thanks!