Why does Python have a maximum recursion depth?

Python has a maximum recursion depth, but no maximum iteration depth. Why is recursion restricted? Wouldn't it be more natural to treat recursion like iteration, and not restrict the number of recursive calls?

Let me just say that the source of this issue came from trying to implement a stream (see this question for more details about streams). For example, say we want to write a stream to produce the natural numbers:

def stream_accum(s, n): # force the stream to a list of length n
    def loop(s, acc):
        if len(acc) == n:
            return acc
        hd, tl = s()
        return loop(tl, acc + [hd])
    return loop(s, [])


def nats():
    def loop(n):
        return n, lambda: loop(n+1)
    return loop(1)

The recursive definition of streams is quite appealing. However, I guess the better/more pythonic approach would be to use generators.

Solution 1:

There are actually a few issues here.

First, as NPE's answer nicely explains, Python doesn't eliminate tail calls, so many functions that would allow unlimited recursion in, say, Scheme are limited in Python.

Second, as again as explained by NPE, calls that can't be eliminated take up space on the call stack. And, even in languages that do TCE, there are plenty of recursive functions that can't be treated like iteration. (Consider the naive Fibonacci function that recursively calls itself twice.)

But why is the call stack a finite resource in the first place? Python stack frames can at least in principle be implemented on the heap and linked together (see Stackless for an existence proof of that principle), and in a 64-bit memory space, there's room for a whole lot more than 1000 stack frames. (In fact, even the C stack on almost any modern platform can hold a whole lot more than 1000 recursive Python interpreter calls.)

Part of the reason is historical: the stock Python interpreter uses the fixed C stack to call itself recursively whenever you make a recursive call, and it was originally designed for 32-bit (and even 24- or 20-bit) platforms where that C stack is pretty small.

But that could have been changed, and Python 3.0 would have been a perfect place to change it. So, why didn't they? Because they made a conscious language design decision. In Pythonic code, recursion is generally very shallow (e.g., code like os.walk that traverses shallow tree structures); if your function hits a depth of anywhere near 1000, it's more likely to be a bug than to be intentional. So, the limit stays. Of course this is a bit circular—if they removed the limit (and, especially, if they eliminated tail calls), deeper recursion would become more idiomatic. But that's kind of the point—Guido doesn't want a language where deep recursion is idiomatic. (And most of the Python community agrees.)

Solution 2:

This is not unique to Python, and has to do with each call taking space on the call stack, and the size of the stack being limited.

Iteration alone does not consume stack space and is therefore not subject to this limit.

Not every recursive call needs to consume stack space. For example, some languages can automatically transform tail recursion into iteration. However, CPython chooses not do that (Does Python optimize tail recursion?).

You can increase the maximum depth of the Python call stack by calling sys.setrecursionlimit.

Solution 3:

Recursion requires space on the call stack, which is limited in size. Code which used too many levels of recursion will give an error called a stack overflow (also made famous by some obscure website). Python seems to limit this (a bit arbitrarily) to 1000 levels or so, but this can be increased by setting sys.setrecursionlimit.

Iteration uses something like a for-loop, which is implemented by incrementing some counter and conditionally setting the instruction pointer back to the beginning of the loop. This is constant in memory.