Perhaps surprisingly, you can convert many recursive algorithms into equivalent iterative versions using a series of simple mechanical steps. For example, if we start with the naive recursive implementation of our beloved fib function,<p><pre><code> def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
</code></pre>
we can arrive at the iterative (dynamic-programming) version that follows,<p><pre><code> def fib(n):
fibn1, fibn2 = (0, 1)
for _ in xrange(n):
fibn1, fibn2 = fibn2, fibn1 + fibn2
return fibn1
</code></pre>
through the following steps: <a href="https://gist.github.com/tmoertel/5798134" rel="nofollow">https://gist.github.com/tmoertel/5798134</a><p>If you're interested in this kind of thing, I'm writing a series of articles on converting recursive algorithms into iterative algorithms. The initial article: <a href="http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html" rel="nofollow">http://blog.moertel.com/posts/2013-05-11-recursive-to-iterat...</a>