13

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.

Improve this question
1
  • 3
    The "appealing" recursive solution has a number of unappealing aspects. First, it has O(n**2) behavior because you are continually building new lists to extend them. Second, it's overly complex given that you can simply iterate to produce natural numbers. This is an example of writing Python as if it were Scheme or Haskell. Different languages are good at different things. Use iteration. Commented Nov 11, 2014 at 20:57

4 Answers 4

Reset to default
27

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.)

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

note that: " You can increase the maximum depth of the Python call stack by calling sys.setrecursionlimit"
But why is deep recursion not preferred? Backtracking codes seem to be lot more nuanced than recursive codes
21

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.

Improve this answer

1 Comment

The size of the stack isn't really limited. (Except in that the heap is limited.) Python chooses to limit it intentionally.
7

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.

Improve this answer

Comments

1

It's not a Python language specification, but a CPython implementation detail. Older version of the other implementation Python, PyPy, doesn't use Stack, and has no recursion depth limit.

https://doc.pypy.org/en/latest/stackless.html#recursion-depth-limit

You may try using PyPy to interpert your Python script if the maximum recursion depth in CPython doesn't satisfy your need.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.