What are the limits of recursion in Python, and when should you choose a loop?

Short answer

Every call uses a stack frame, the default recursion depth limit is about 1000, and Python does not optimize tail calls, so a loop or an explicit stack suits deep data better.

Explanation

When the limit is exceeded Python raises RecursionError. Blindly raising it with sys.setrecursionlimit can crash the process by overflowing the C stack. Use recursion when the depth is small and bounded and it simplifies the code (such as walking a balanced tree), and convert it to a loop with an explicit stack for structures that may be very deep. functools.cache can speed up repeated calls but it does not solve the depth problem.

Code example

def walk(root):
    stack = [root]
    while stack:  # No call-depth limit
        node = stack.pop()
        yield node
        stack.extend(reversed(node.children))

Common mistakes

• Raising the recursion limit to a huge value to hide a design problem.
• Assuming Python optimizes tail recursion as some functional languages do.

Follow-up questions

• What does it mean that functions in Python are first-class objects?

Sources

• Python documentation — sys.setrecursionlimit