why memoizing is faster

[Andrea Crotti]

I was showing a nice memoize decorator to a friend using the classic
fibonacci problem.

--8<---------------cut here---------------start------------->8---
  def memoize(f, cache={}):
      def g(*args, **kwargs):
          # first must create a key to store the arguments called
          # it's formed by the function pointer, *args and **kwargs
          key = ( f, tuple(args), frozenset(kwargs.items()) )
          # if the result is not there compute it, store and return it
          if key not in cache:
              cache[key] = f(*args, **kwargs)
  
          return cache[key]
  
      return g
  
  # without the caching already for 100 it would be unfeasible
  @memoize
  def fib(n):
      if n <= 1:
          return 1
      else:
          return fib(n-1) + fib(n-2)
  
--8<---------------cut here---------------end--------------->8---


It works very well, but he said that the iterative version would be
anyway faster.

But I tried this
  
--8<---------------cut here---------------start------------->8---
  def fib_iter(n):
      ls = {0: 1, 1:1}
      for i in range(2, n+1):
          ls[i] = ls[i-1] + ls[i-2]
  
      return ls[max(ls)]
--8<---------------cut here---------------end--------------->8---

and what happens is surprising, this version is 20 times slower then the
recursive memoized version.

I first had a list of the two last elements and I thought that maybe the
swaps were expensive, now with a dictionary it should be very fast.

Am I missing something?
Thanks, 
Andrea