How Does Recursion Work in Python?

Every recursive function needs two things. It needs a base case that stops the recursion, and it needs a recursive case that calls the function again with a smaller problem.

def total(values):
    if not values:              # base case
        return 0
    return values[0] + total(values[1:])


print(total([1, 2, 3, 4]))    # 10

The call total([1, 2, 3, 4]) adds the first element to the result of total([2, 3, 4]), which adds 2 to the result of total([3, 4]), which adds 3 to the result of total([4]), which adds 4 to the result of total([]). The empty list is the base case, and it returns 0. The calls then unwind in the opposite order, and each frame adds its own element to the value that the frame below it returned, until the outermost call finally returns 10.

Each of those calls is a stack frame that holds its own arguments and its own local variables. The frames are pushed when the call is made and popped when the call returns, and the total memory that is used grows with the depth of the recursion.

There are two things to notice in this implementation. The list slicing on each call does a lot of work, so the whole function is much slower than it looks. And Python's own recursion limit would stop a deep recursion long before a large list became a real problem. A cleaner version takes an index instead of slicing.

def total_index(values, index=0):
    if index == len(values):
        return 0
    return values[index] + total_index(values, index + 1)

This version does the work in one pass, and the price is one extra parameter.

Without a base case that can actually be reached, the recursion keeps going until it hits Python's recursion limit, and then Python raises a RecursionError. You can watch it happen and catch it like any other exception.

import sys


def endless(n):
    return endless(n + 1)


print('limit:', sys.getrecursionlimit())

try:
    endless(0)
except RecursionError as err:
    print('RecursionError:', err)

The limit line prints 1000, which is the default value. The except block then catches the RecursionError and prints its message, which is "maximum recursion depth exceeded".

There is a limit at all because every recursive call uses space on the C stack. Without a limit, a runaway recursion would eventually overflow that stack and crash the whole interpreter, instead of raising an exception that you could catch. The default of 1000 is a compromise. It is deep enough for the realistic recursive algorithms, and shallow enough to leave room for the other frames that are already on the stack.

You can raise the limit with sys.setrecursionlimit, but you have to be careful. The real C stack is finite, so if you set the limit high enough to go past it you get a hard crash instead of a RecursionError, which means a segmentation fault rather than an exception. On Linux the main thread has a large stack, so a much higher limit is usually survivable there. A thread that you create with threading.Thread has a much smaller default stack, and raising the limit in that thread is a reliable way to crash the whole process.

There are two practical notes to finish with. Python does not optimise tail calls, so a recursive function written in tail-call style still uses one frame per call. And since Python 3.11 the frames are much cheaper to create, so the default limit is less likely to be reached than it used to be in earlier versions.

Recursion works when a function calls itself with a smaller input until it reaches a base case. Every call pushes a frame onto the call stack, and every return pops one frame off it. That stack is what makes the order of operations work, because the innermost call finishes first, and its return value is handed back to the caller above it, which then carries on.

Two ingredients are always necessary. The base case has to stop the work, and the recursive case has to move towards it. Get either one wrong and you get infinite recursion, which Python turns into a RecursionError once the limit is reached.

The default recursion limit is 1000 nested calls. You can read it with sys.getrecursionlimit and you can change it with sys.setrecursionlimit. The limit protects the C stack of the interpreter and not your program. Each Python frame uses real stack space underneath it, so without a limit a runaway recursion would crash the process outright instead of raising an exception that you could catch. Because the frames became much cheaper in Python 3.11, the practical ceiling for one thread on Linux is often well above the default of 1000, but the limit that the language itself applies is still 1000 unless you change it.

For an interview, the honest recommendation is this. Use recursion when the problem is naturally recursive and the depth is small, such as trees, nested structures, or divide and conquer. Use a loop when the depth could be large. The Python stack is a real resource, and a recursive walk over a linked list of a million elements will not fit inside it.