The main reason people need to keep explaining memoization is that they insist on using the unnecessarily obfuscating academic term "memoization", instead of the more commonly understood term "caching".

This isn't right:

    fib_val = fib_mem(n-1) + fib_val(n-2)

Note that we can use the @functools.lru_cache(None) to easily benefit from memoization.

The code in this post seem a bit unpythonic and "improvable" for me:

- "if len(list) > n" should probably be "if n in list".

- The function has a side effect (changing the list), this is to be avoided when avoidable

- Memoization is not part of the logic, thus is better done with a decorator (which would solve above side effect issue)

I like to use dicts for memoization...This runs about 8% faster on my machine than OP's solution:

    memo5 = {0:0,1:1}
    def fib_mem5(n):    
        try:
            return memo5[n]
        except KeyError:
            memo5[n] = fib_mem5(n-1)+fib_mem5(n-2)         
        return memo5[n]

  memo6 = {0:0,1:1}
  def fib_mem6(n):    
      if n in memo6:
          return memo6[n]    
      memo6[n] = fib_mem6(n-1)+fib_mem6(n-2)         
      return memo6[n]

Fibonacci really doesn't need memoization since you can implement it efficiently by keeping just the last two values on the stack. Dynamic programming (like the knapsack problem) is a better example.

Is there a way to fix the recursion depth problem with this solution?

To me, the memoized version is more clear and should be just as efficient as the iterative version. However, this version of fib_mem dies before fib_mem(1000)!

Apparently, you can increase the recursion depth limit using the sys module. Is that the right thing to do? And, if you do it, are there guidelines for doing so without causing memory problems?

You can also memoize recursive functions transparently with a memoizing fixed-point (Y) combinator:

http://matt.might.net/articles/implementation-of-recursive-f...

The example is also Fibonacci.

I like this article on memoization - http://www.agillo.net/getting-groovy-with-fibonacci/

The diagrams make it easy to understand. It is in groovy though.