[pbh]

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?

[pash]

Yes, use sys.setrecursionlimit(n) to change the max recursion depth. Max supported stack depth of course varies by platform.

In many cases, a better solution is to implement tail recursion, which can be done quite easily. See http://paulbutler.org/archives/tail-recursion-in-python/ .