[tmoertel]

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,

    def fib(n):
        if n < 2:
            return n
        return fib(n - 1) + fib(n - 2)

we can arrive at the iterative (dynamic-programming) version that follows,

    def fib(n):
        fibn1, fibn2 = (0, 1)
        for _ in xrange(n):
            fibn1, fibn2 = fibn2, fibn1 + fibn2
        return fibn1

through the following steps: https://gist.github.com/tmoertel/5798134

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: http://blog.moertel.com/posts/2013-05-11-recursive-to-iterat...

[mechagodzilla]

Here is the Fibonacci sequence calculated by a literal series of mechanical steps: http://www.chrisfenton.com/the-turbo-entabulator/

[benjamincburns]

Edit:

Doh - I'm a moron! You're using a recurrence relation, which has the nice property of never computing the same sub-solution twice. I'll leave this here as a reminder to think before I nitpick next time.

Original:

Apologies to nitpick, but your iterative python solution isn't DP. DP hinges on the idea of never computing the answer to the same problem twice. For it to be DP, it would need to memoize subproblem solutions and refer to the solution cache rather than recompute the solution to every subproblem in the tree every time.

This solution fits the bill, although it can probably be written a bit more elegantly:

  fibs = {0: 1, 1: 1}
  def fib(n):
      global fibs
      stack = []
      for a in xrange(n,0,-1):
          if a in fibs:
              stack.reverse()
              for item in stack:
                  fibs[item] = fibs[a] + fibs[a-1]
                  a = item
              break
          else:
              stack.append(a)
      return fibs[n]