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.

## 1 comment:

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!

Post a Comment