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.