Recursion in Python — theory with the canteen queue, the call stack and a power that gets fast (and the function that never stopped asking)

The first recursive function I wrote had to count how many people were ahead of me in the university canteen queue. The idea seemed beautiful: “the people ahead of me are one (the person right in front) plus the people ahead of them”. I wrote it exactly like that, in one line, and ran it with a queue of three people:

def count_ahead(ahead):
    return 1 + count_ahead(ahead[:-1])


queue = ["Ana", "Luis", "Marta"]
print(count_ahead(queue))

Traceback (most recent call last):
  File "hook.py", line 6, in <module>
    print(count_ahead(queue))
          ^^^^^^^^^^^^^^^^^^
  File "hook.py", line 2, in count_ahead
    return 1 + count_ahead(ahead[:-1])
               ^^^^^^^^^^^^^^^^^^^^^^^
  File "hook.py", line 2, in count_ahead
    return 1 + count_ahead(ahead[:-1])
               ^^^^^^^^^^^^^^^^^^^^^^^
  File "hook.py", line 2, in count_ahead
    return 1 + count_ahead(ahead[:-1])
               ^^^^^^^^^^^^^^^^^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

“A thousand calls? There are only three people.” What I had written was not false, but it was incomplete: I had told every person to ask the one in front, and I had told nobody when to stop. When the queue became empty, ahead[:-1] kept returning an empty list, the function asked again, and so on until Python got tired and pulled the plug with a RecursionError.

Today we understand what recursion is, why every recursive function needs a base case and a general case, how calls pile up in memory, why two recursive solutions to the same problem can be very different in depth and efficiency, and how all this applies to sequences, to linked lists and to the immersion technique. The example that goes with us all the way is the canteen queue. If you come from mutability, copies and matrices, it helps to have slices fresh in your mind: you will use them in almost every line here. And when you finish, the recursion practice is waiting for you with three complete programs.

What is recursion?

Recursion is a way of solving problems that consists of splitting the problem into smaller versions of itself, until you reach one so small that it is solved directly. In programming, it becomes a function that calls itself.

Picture the canteen queue. You arrive at the end and want to know how many people are ahead of you, but you cannot see the front clearly. So you ask the person right in front of you: “how many people are ahead of you?”. They do not know either, so they ask theirs, and that one asks theirs… until the question reaches the first person in the queue, who has nobody ahead and answers “zero”. That answer travels back: the second person says “1”, the third says “2”… and the final answer reaches you.

Look at the two pieces of that story:

• The base case: the first person in the queue knows the answer without asking anyone (zero). It is the point where the recursion stops.
• The general case: anybody else answers “1 (the person in front) + whatever the person in front tells me”. They solve their problem using the answer to a smaller problem (a queue with one person fewer).

In Python it looks like this:

def count_ahead(ahead):
    """Counts the people ahead in the canteen queue."""
    if ahead == []:                           # base case: nobody there
        return 0
    else:                                     # general case
        return 1 + count_ahead(ahead[:-1])    # the one ahead + their ones


queue = ["Ana", "Luis", "Marta", "Pablo"]
print(count_ahead(queue))
print(count_ahead(["Ana"]))
print(count_ahead([]))

4
1
0

Between the lines:

• ahead is the list of the people ahead of you, from the first one to the one right in front of you. That last person is ahead[-1], and the people ahead of them are ahead[:-1] (everybody except the last one).
• Base case: if ahead is empty, there is nobody and the answer is 0, without calling anyone.
• General case: 1 + count_ahead(ahead[:-1]). The function calls itself with a list one person shorter. Every call is closer to the base case, and that guarantees the recursion ends.
• It works with four people, with one and with none. The base case makes sure the empty queue has an answer too.

Base case and general case: how to think a recursive solution

The hard part of recursion is not writing it, but thinking it. In class we were given four questions that work for almost any problem. Let us apply them to computing the total the queue pays (a list of tray prices):

Question	For the total of the trays
What determines the size of the problem?	The number of trays in the list
How do I move to a smaller version?	By removing the first one: prices[1:]
When can I not split any further (base case)?	When there are no trays: the total is 0
How do I combine the small solution with what I have left?	By adding the price of the first one: prices[0] + total(prices[1:])

With those four answers, the function almost writes itself. And the same recipe works to count how many vegetarian menus there are in the queue:

def total(prices):
    """Adds up the prices of all the trays."""
    if prices == []:                      # no trays, nothing to pay
        return 0
    return prices[0] + total(prices[1:])  # the first one + the total of the rest


def count_vegetarian(menus):
    """Counts how many vegetarian menus there are in the queue."""
    if menus == []:
        return 0
    if menus[0] == "vegetarian":          # the first one counts
        return 1 + count_vegetarian(menus[1:])
    return count_vegetarian(menus[1:])    # the first one does not count


print(total([5.50, 5.00, 2.25]))
print(count_vegetarian(["normal", "vegetarian", "normal", "vegetarian"]))

12.75
2

Between the lines:

• Both functions have the same shape: an if for the base case and a return that combines the first element with the call on the rest. That shape is the pattern of almost every recursive function over lists.
• In total, the combination is a sum: prices[0] + total(prices[1:]). For [5.50, 5.00, 2.25] it gives 5.50 + (5.00 + (2.25 + 0)).
• In count_vegetarian there are two general cases: if the first one is vegetarian, it adds 1; if not, it adds nothing. In both of them the call receives menus[1:], so the list always shrinks.
• Here we use the “first and rest” view (items[0] and items[1:]), while in the queue we used “rest and last” (ahead[:-1]). Both are valid: what matters is that the recursive call receives something smaller.

The call stack: what happens inside

When a function calls itself, the previous call does not finish: it stays waiting for the answer. Python keeps every pending call, with its own variables, in a structure called the call stack: the last one in is the first one out, like a pile of trays.

To see it, we add a level parameter that only serves to indent the output, and a couple of print calls:

def count_ahead(ahead, level=0):
    indent = "    " * level
    print(f"{indent}How many are ahead of you? {ahead}")
    if ahead == []:
        print(f"{indent}Nobody: I answer 0")
        return 0
    answer = 1 + count_ahead(ahead[:-1], level + 1)
    print(f"{indent}I answer {answer}")
    return answer


print("Total:", count_ahead(["Ana", "Luis", "Marta"]))

How many are ahead of you? ['Ana', 'Luis', 'Marta']
    How many are ahead of you? ['Ana', 'Luis']
        How many are ahead of you? ['Ana']
            How many are ahead of you? []
            Nobody: I answer 0
        I answer 1
    I answer 2
I answer 3
Total: 3

Read the output from top to bottom:

• Way down: every call asks and stays waiting. Notice how the indentation grows: there are four calls active at the same time, each with its own ahead. None of them has finished yet.
• Base case: the fourth call receives [] and is the first one that can answer without asking: 0.
• Way back up: the answers travel through the stack in reverse. The third call receives the 0 and answers 1; the second receives the 1 and answers 2; the first receives the 2 and answers 3.
• What comes before the recursive call runs on the way down; what comes after runs on the way back. That is why the “How many are ahead of you?” lines come out in order and the “I answer” lines come out reversed.

The stack limit

The stack is not infinite. Python limits how many calls can be waiting at the same time:

import sys


def count_ahead(ahead):
    if ahead == []:
        return 0
    return 1 + count_ahead(ahead[:-1])


print(sys.getrecursionlimit())
print(count_ahead(["student"] * 500))

1000
500

The default limit is 1000. With 500 people in the queue, the stack reaches 501 calls and everything is fine. With a queue of 5000, the function would be correct, but Python would raise RecursionError before reaching the base case. It is exactly the error at the start of the article, except that there it was not caused by a huge queue, but by a recursion that never stopped.

Depth and efficiency: three ways of computing a power

Two recursive solutions to the same problem can behave very differently. The classic example (and the one we got in class) is the power base ** exp. We look at it with three versions, and with a calls variable that counts how many times each function is called:

calls = 0


def linear_power(base, exp):
    global calls
    calls += 1
    if exp == 0:
        return 1
    return base * linear_power(base, exp - 1)


def double_power(base, exp):
    global calls
    calls += 1
    if exp == 0:
        return 1
    if exp % 2 == 0:
        return double_power(base, exp // 2) * double_power(base, exp // 2)
    return base * double_power(base, exp // 2) * double_power(base, exp // 2)


def fast_power(base, exp):
    global calls
    calls += 1
    if exp == 0:
        return 1
    half = fast_power(base, exp // 2)     # a single call
    if exp % 2 == 0:
        return half * half
    return base * half * half


for exp in [8, 16, 32]:
    calls = 0
    result = linear_power(2, exp)
    print(f"linear  2^{exp} = {result}: {calls} calls")
    calls = 0
    result = double_power(2, exp)
    print(f"double  2^{exp} = {result}: {calls} calls")
    calls = 0
    result = fast_power(2, exp)
    print(f"fast    2^{exp} = {result}: {calls} calls")

linear  2^8 = 256: 9 calls
double  2^8 = 256: 31 calls
fast    2^8 = 256: 5 calls
linear  2^16 = 65536: 17 calls
double  2^16 = 65536: 63 calls
fast    2^16 = 65536: 6 calls
linear  2^32 = 4294967296: 33 calls
double  2^32 = 4294967296: 127 calls
fast    2^32 = 4294967296: 7 calls

All three give the same result, but look at the calls:

• **linear_power** uses base ** exp = base * base ** (exp - 1). Each call makes one call with the exponent one smaller, so for 2^8 there are 9 calls (from 8 down to 0), and all of them are active at the same time: the depth of the recursion is 9. Calls and depth grow like the exponent.
• **double_power** uses base ** exp = base ** (exp // 2) * base ** (exp // 2). The exponent is halved on each level, so the depth is very small (for 2^8: 8, 4, 2, 1, 0, that is, 5 levels). But each call makes two calls, and the number of calls doubles on every level: 31 for 2^8, 127 for 2^32. It uses little memory, but it works much harder than the linear one.
• **fast_power notices that the two calls of the double version compute exactly the same thing. It makes it only once**, stores the result in half and multiplies it by itself. It keeps the small depth of the double version and leaves a single call per level: 5 calls for 2^8 and only 7 for 2^32.
• global calls lets the function change the variable outside; we use it only to measure. In your normal functions, avoid global.

The difference has two sides that are worth separating:

Measure	What it is	Linear	Double	Fast
Depth	How many calls are active at the same time (memory)	Grows like exp	Grows like log₂(exp)	Grows like log₂(exp)
Number of calls	How many are made in total (time)	exp + 1	Doubles on every level	One per level

Recursion over sequences: first and rest

Many structures can be seen recursively. A non-empty list is “a first element followed by a smaller list”, and that fits the recursive pattern. Two examples: looking for someone in the queue and looking for a ticket number in a sorted list.

def is_in(queue, name):
    """Is name in the queue? Look at the first one and ask the rest."""
    if queue == []:
        return False
    if queue[0] == name:
        return True
    return is_in(queue[1:], name)


def has_ticket(tickets, ticket):
    """Binary search in a SORTED list of tickets."""
    if tickets == []:
        return False
    mid = len(tickets) // 2
    if tickets[mid] == ticket:
        return True
    if tickets[mid] > ticket:                        # it is in the left half
        return has_ticket(tickets[:mid], ticket)
    return has_ticket(tickets[mid + 1:], ticket)     # it is in the right half


queue = ["Ana", "Luis", "Marta", "Pablo"]
print(is_in(queue, "Marta"), is_in(queue, "Lucía"))
tickets = [3, 8, 12, 15, 21, 27, 30, 34]
print(has_ticket(tickets, 27), has_ticket(tickets, 20))

True False
True False

Between the lines:

• **is_in is a linear search: it looks at the first person in the queue and, if they are not the one you are looking for, asks the rest. It has two base cases**: the empty queue (not there, False) and finding the name (there it is, True). In the worst case, it goes through the whole queue, so its depth grows with the length of the list.
• **has_ticket is a binary search (also called dichotomic), which only works if the list is sorted. It looks at the middle element: if it is the ticket, it has found it; if it is greater, the ticket can only be in the left half; if it is smaller, in the right half. Each call discards half** of the list, so the depth grows like log₂ of the length: for 8 tickets, 5 calls at most (with 8, 4, 2, 1 and 0 elements).
• Both of them use slices (queue[1:], tickets[:mid]) to pass the smaller part. It works, but it has a hidden cost that we will see shortly.

Linked lists: a truly recursive structure

So far we have looked at lists recursively. But you can also build structures that are recursive by definition. In class we saw the linked list made with tuples: each link is a tuple (value, rest), where rest is another linked list, and the empty list is the empty tuple ().

The canteen queue fits perfectly: “Ana, and behind her, Luis’s queue; and behind Luis, Marta’s; and behind Marta, nobody”.

empty = ()                     # an empty queue is an empty tuple
queue = ("Marta", empty)       # Marta and, behind her, nobody
queue = ("Luis", queue)        # Luis and, behind him, the previous queue
queue = ("Ana", queue)
print(queue)


def length(queue):
    if queue == ():
        return 0
    name, rest = queue
    return 1 + length(rest)


def is_in(queue, wanted):
    if queue == ():
        return False
    name, rest = queue
    if name == wanted:
        return True
    return is_in(rest, wanted)


print(length(queue))
print(is_in(queue, "Luis"), is_in(queue, "Pablo"))

('Ana', ('Luis', ('Marta', ())))
3
True False

Between the lines:

• The queue is built from the back to the front: first Marta (with the empty queue behind her), then Luis in front of Marta and, finally, Ana. The print shows the nested tuples: ('Ana', ('Luis', ('Marta', ()))).
• Each tuple is called a node or link: it stores a name and a reference to the next node. The queue variable actually points only to the first one.
• name, rest = queue unpacks the node into its two parts. From there, the functions follow the usual pattern: base case with the empty queue () and general case with rest.
• An advantage: passing rest to the recursive call copies nothing, because rest already is the smaller queue. A disadvantage: you cannot go straight to position 2 as with items[2]; to reach the third node, you have to go through the two before it.

Recursive immersion: solving a more general problem

Let us go back to the binary search. Each tickets[:mid] and each tickets[mid + 1:] creates a new list: you saw it in the previous topic, a slice is a copy. To search a list of a million tickets, the first call would copy half a million elements just to discard the other half. Besides, the function only tells you whether the ticket is there, not where: the position inside a slice is not the position in the original list.

The solution we were given is called immersion: instead of solving “is the ticket in the list?”, we solve a more general problem that contains it, “is the ticket between positions low and high of the list?”. The list is no longer copied; only the two indexes change:

def search_range(tickets, ticket, low, high):
    """Looks for ticket between positions low (included) and high (excluded)."""
    if low >= high:                                   # empty zone
        return -1
    mid = (low + high) // 2
    if tickets[mid] == ticket:
        return mid
    if tickets[mid] > ticket:
        return search_range(tickets, ticket, low, mid)
    return search_range(tickets, ticket, mid + 1, high)


def find_ticket(tickets, ticket):
    """Returns the position of ticket in the sorted list, or -1."""
    return search_range(tickets, ticket, 0, len(tickets))


tickets = [3, 8, 12, 15, 21, 27, 30, 34]
print(find_ticket(tickets, 27))
print(find_ticket(tickets, 3), find_ticket(tickets, 34))
print(find_ticket(tickets, 20))

5
0 7
-1

Between the lines:

• search_range always receives the whole list and two numbers that mark the zone still to be checked: from low (included) to high (excluded), just like in a range.
• The base case is now low >= high: the zone is empty, so the ticket is not there and we return -1.
• Since we work with the real positions, when we find it we can return mid: the position in the original list. Ticket 27 is at position 5.
• find_ticket is the function everybody uses: it keeps the simple interface (list and ticket) and immerses the problem in the general one by calling it with the whole zone, 0 and len(tickets). That is why it is called immersion: the original problem is a particular case of the general one.

The same idea works for any traversal. If instead of cutting the queue with slices you carry the position as a parameter, you do not copy anything either:

def count_from(queue, pos):
    """Counts the people in the queue from position pos."""
    if pos == len(queue):
        return 0
    return 1 + count_from(queue, pos + 1)


def count(queue):
    return count_from(queue, 0)


print(count(["Ana", "Luis", "Marta", "Pablo"]))

4

Recursive or iterative?

Everything you can do with recursion can be done with loops, and the other way around. So, when should you use each one?

Use recursion when…	Use a loop when…
The problem is defined recursively (powers, binary search, nested structures)	The problem is a simple traversal (adding, counting, searching a list)
The structure is recursive (linked lists, lists of lists of variable depth)	The structure is flat and can be very long
The depth is small (for example, logarithmic)	The depth could go over the limit of 1000 calls
The recursive solution is much clearer	The loop solution is just as clear

In Python, counting a queue or adding up a list is more efficient with a loop (or with len and sum). Recursion shines when each call splits the problem (binary search, fast power) or when the structure nests data inside data, as you will see in the practice with a group order full of sub-orders.

Watch it step by step in Python Tutor

Python Tutor runs the code line by line and draws each call as a frame with its own variables: it is the best way to see the call stack. Choose Python 3 and paste this program:

def count_ahead(ahead):
    if ahead == []:
        return 0
    return 1 + count_ahead(ahead[:-1])


queue = ["Ana", "Luis", "Marta"]
total = count_ahead(queue)
print(total)

Expected output:

3

What to watch, step by step:

1. In the first call, a count_ahead frame appears with ahead = ["Ana", "Luis", "Marta"]. When it reaches return 1 + …, the function does not finish: a second frame appears below it.
2. Keep going: you will see four stacked frames, each with its own ahead (with three names, two, one and none). Four different variables with the same name.
3. In the fourth frame, ahead is [] and the base case is met. Python Tutor shows Return value: 0 and that frame disappears.
4. Now watch the way back: the third frame receives the 0 and returns 1, the second returns 2 and the first returns 3. The stack empties in the reverse order to the one in which it filled up.
5. When the last frame finishes, total is 3 in the global frame and the print shows it.

Summary

Concept	The essentials
Recursion	A function that calls itself with a smaller version of the problem
Base case	The case solved without recursive calls; without it, the recursion does not end
General case	Solves the problem by combining a call on something smaller
Four questions	Size, how to reduce it, when it cannot be reduced, how to combine
Call stack	Each pending call waits with its own variables; limit of 1000
RecursionError	The base case is missing, never reached, or the recursion is too deep
Depth	Calls active at the same time (memory)
Number of calls	Calls in total (time); repeating a call multiplies it
First and rest	items[0] and items[1:]: the pattern of recursive functions over lists
Binary search	In a sorted list, discards half on every call
Linked list	Tuples (value, rest) ending in ()
Immersion	Solving a more general problem (with indexes or accumulators) and calling it from the original one

Three ideas to take away:

1. Every recursive function has two parts: a base case that stops and a general case that gets closer to it. If the recursive call does not receive something smaller, the function will never end.
2. Calls pile up and wait. What comes before the call runs on the way down and what comes after, on the way back. Following that stack with a trace or with Python Tutor is how you understand any recursive function.
3. Not every recursion costs the same. Splitting the problem in half reduces the depth; not repeating calls reduces the work; and immersion with indexes avoids copying lists on every call.

In the recursion practice you will apply all this to the canteen queue, to a ticket search with a trace and to a group order with sub-orders inside. Then, the exercises will put you to the test. And in the next topic come associative containers: dictionaries.

Next step: practiceRecursion in Python — practice with the canteen queue, a ticket search with a trace and a group order (and the ticket that was at the wrong position)

Did this article help you? Here is how you can support SergioLearns →