Recursion in Python — exercises with the canteen queue, a reversed exit and a linked queue (and the extra person who never existed)

To get ready for the exam, I wrote a recursive function that counted the people in the canteen queue. I tried it with three names and it told me 4. I tried it with one and it told me 2. With the empty queue, 1: a ghost person who always showed up, however empty the queue was. I checked the general case twenty times, because I was sure the bug was that 1 +.

The general case was fine. The bug was in the base case: I had written return 1 when the queue was empty, as if an empty queue had someone in it. That 1 sneaked into the end of every sum, in every call. It is the kind of bug of this topic: the recursion looks correct and the output almost makes sense.

Today we practise with three exercises of increasing difficulty, three snippets to debug (the ghost person included) and a cheat sheet to take away. These exercises use the recursion theory and review the practice. You can do them without those, but it will be harder.

How to use this article

1. Read the statement of a level and do not look at the solution yet.
2. Write your version, run it and compare your output with the expected one.
3. If you get stuck, look only at the 🔵 hint and try again.
4. When you finish, compare with the solution and pay attention to why it is done that way, not only to whether it gives the same output.

Level 1 · Basic: the countdown and the trays bill

Statement. Write three recursive functions:

• countdown(ahead), which prints There are N ahead of me from ahead down to 1 and, at the end, It's my turn!. It returns nothing.
• total(prices), which returns the sum of a list of prices.
• count_expensive(prices, limit), which returns how many prices are greater than limit.

Try them with countdown(3) and with the list [5.50, 2.25, 5.00, 1.50, 5.50], showing the total with two decimals and the trays over 5 €.

Expected output:

There are 3 ahead of me
There are 2 ahead of me
There are 1 ahead of me
It's my turn!
Total: 19.75 €
Trays over 5 €: 2

Level 2 · Intermediate: leaving the canteen

Statement. When lunch is over, the queue leaves the canteen in reverse order and some people leave earlier. Write two recursive functions that return new lists without changing the original:

• reverse_queue(queue), which returns the queue backwards.
• remove_person(queue, name), which returns the queue without any appearance of name (it may appear several times or not at all).

Try them with queue = ["Ana", "Luis", "Marta", "Luis", "Pablo"]: reverse the queue, remove Luis, remove Lucía (who is not there) and, at the end, show the original queue to check that it has not changed.

Expected output:

['Pablo', 'Luis', 'Marta', 'Luis', 'Ana']
['Ana', 'Marta', 'Pablo']
['Ana', 'Luis', 'Marta', 'Luis', 'Pablo']
['Ana', 'Luis', 'Marta', 'Luis', 'Pablo']

Level 3 · Challenge: a linked queue where someone cuts in

Statement. Represent the queue as a linked list of tuples (name, rest), ending in (), as in the theory. Write four recursive functions:

• from_list(items): turns a Python list into a linked queue.
• length(queue): the number of people.
• to_text(queue): returns a string with the format Ana -> Luis -> Marta, or (empty) if there is nobody.
• cut_in(queue, name, in_front_of): returns a new queue where name is right in front of in_front_of. If in_front_of is not in the queue, name goes at the end.

Create the queue of Ana, Luis and Marta, show it as it is and with its length and its text. Then, let Pablo cut in front of Marta, let Sara cut in front of Lucía (who is not there), show the original queue to check that it has not changed and, finally, the text of an empty queue.

Expected output:

('Ana', ('Luis', ('Marta', ())))
3 people: Ana -> Luis -> Marta
Ana -> Luis -> Pablo -> Marta
Ana -> Luis -> Marta -> Sara
Ana -> Luis -> Marta
(empty)

What’s wrong here?

Three snippets with one bug each. Before reading the explanation, do two things: predict whether it raises an error and, if it does not, what it prints.

Snippet 1

count.py

def count(queue):
    if queue == []:
        return 1
    return 1 + count(queue[1:])


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

*Think before you go on: there are three people in the queue. What does python3 count.py print?*

Explanation. There is no error, but the result is wrong:

4

It is the ghost person from the beginning. The base case says that an empty queue has 1 person, and that 1 is added at the end of the chain: 1 + (1 + (1 + 1)). Every queue comes out with one extra person.

Fix. An empty queue has 0 people:

def count(queue):
    if queue == []:
        return 0                 # an empty queue has 0 people
    return 1 + count(queue[1:])


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

3
0

Snippet 2

total.py

def total(prices):
    if prices == []:
        return 0
    return prices[0] + total(prices[0:])


print(total([5.50, 5.00, 2.25]))

Does it raise an error? What does it print? We want to add up three trays.

Explanation. This time there is an error:

Traceback (most recent call last):
  File "total.py", line 7, in <module>
    print(total([5.50, 5.00, 2.25]))
          ^^^^^^^^^^^^^^^^^^^^^^^^^
  File "total.py", line 4, in total
    return prices[0] + total(prices[0:])
                       ^^^^^^^^^^^^^^^^^
  File "total.py", line 4, in total
    return prices[0] + total(prices[0:])
                       ^^^^^^^^^^^^^^^^^
  File "total.py", line 4, in total
    return prices[0] + total(prices[0:])
                       ^^^^^^^^^^^^^^^^^
  [Previous line repeated 995 more times]
  File "total.py", line 2, in total
    if prices == []:
       ^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded in comparison

The slice prices[0:] goes from position 0 to the end, that is, the whole list. The recursive call receives exactly the same list, which never becomes empty, so the base case is never reached and the stack overflows after about a thousand calls. Notice the [Previous line repeated 995 more times]: Python summarises the repeated calls so as not to fill the screen.

Fix. The rest is the list without the first one: prices[1:].

def total(prices):
    if prices == []:
        return 0
    return prices[0] + total(prices[1:])    # the rest: WITHOUT the first one


print(total([5.50, 5.00, 2.25]))

12.75

Snippet 3

is_in.py

def is_in(queue, name):
    if queue == []:
        return False
    if queue[0] == name:
        return True
    is_in(queue[1:], name)


queue = ["Ana", "Luis", "Marta"]
print(is_in(queue, "Ana"))
print(is_in(queue, "Marta"))
print(is_in(queue, "Lucía"))

Does it raise an error? What does it print? Marta is in the queue and Lucía is not.

Explanation. It raises no error, but two of the three answers are None:

True
None
None

With Ana it works because she is first and the return True is met in the first call. With Marta, the function calls itself with the rest, and that call does find Marta and returns True… but the call above does nothing with that answer: it throws it away. Since it reaches the end of the function without a return, it returns None. The same happens with Lucía: the False of the base case gets lost on the way.

Fix. Return what the rest answers:

def is_in(queue, name):
    if queue == []:
        return False
    if queue[0] == name:
        return True
    return is_in(queue[1:], name)       # return what the rest answers


queue = ["Ana", "Luis", "Marta"]
print(is_in(queue, "Ana"))
print(is_in(queue, "Marta"))
print(is_in(queue, "Lucía"))

True
True
False

Solutions

Look at this section only when you have tried the exercise. If your code is different but gives the same output and meets the requirements (recursive functions, no loops), it is also a valid solution.

Level 1 solution

countdown.py

def countdown(ahead):
    """Announces how many are left ahead until it is your turn."""
    if ahead == 0:
        print("It's my turn!")
    else:
        print(f"There are {ahead} ahead of me")
        countdown(ahead - 1)


def total(prices):
    """Adds up the prices of a list of trays."""
    if prices == []:
        return 0
    return prices[0] + total(prices[1:])


def count_expensive(prices, limit):
    """Counts the prices greater than limit."""
    if prices == []:
        return 0
    if prices[0] > limit:
        return 1 + count_expensive(prices[1:], limit)
    return count_expensive(prices[1:], limit)


countdown(3)
prices = [5.50, 2.25, 5.00, 1.50, 5.50]
print(f"Total: {total(prices):.2f} €")
print("Trays over 5 €:", count_expensive(prices, 5))

Why it is done this way:

• countdown returns nothing: it prints. Its base case prints It's my turn! and finishes; the general case prints the line and calls itself with ahead - 1, which gets closer to 0. Since the print comes before the call, the lines come out on the way down, from 3 to 1.
• total is the first-and-rest pattern in its purest form: 0 for the empty list and prices[0] + total(prices[1:]) in the general case. The numbers add up: 5.50 + 2.25 + 5.00 + 1.50 + 5.50 = 19.75.
• count_expensive has two general cases: if the first one is over the limit it adds 1, and if not, it adds nothing. In both, the call receives prices[1:]. The two 5.50 prices count; 5.00 does not, because it is not greater than 5.
• limit is passed the same in every call: it is data that does not change. Only the list changes, which is what makes the problem smaller.

Level 2 solution

leaving.py

def reverse_queue(queue):
    """Returns the queue in reverse order, without changing the original."""
    if queue == []:
        return []
    return reverse_queue(queue[1:]) + [queue[0]]


def remove_person(queue, name):
    """Returns a new queue without any appearance of name."""
    if queue == []:
        return []
    if queue[0] == name:
        return remove_person(queue[1:], name)
    return [queue[0]] + remove_person(queue[1:], name)


queue = ["Ana", "Luis", "Marta", "Luis", "Pablo"]
print(reverse_queue(queue))
print(remove_person(queue, "Luis"))
print(remove_person(queue, "Lucía"))
print(queue)

Why it is done this way:

• reverse_queue follows the hint: it reverses the rest and puts the first one at the end. For ["Ana", "Luis"]: reverse_queue(["Luis"]) + ["Ana"], which is ["Luis"] + ["Ana"]. Concatenating with + creates a new list, so the original is not touched.
• [queue[0]] puts the first name inside a one-element list. Without the brackets, list + "Ana" would raise a TypeError, because you cannot concatenate a list and a string.
• remove_person builds the answer only with what it wants to keep: if the first one is the name, it skips it (it directly returns what comes from the rest); if not, it puts it in front. That is why it removes every appearance of Luis, not only the first one, unlike list.remove.
• Removing Lucía raises no error: if she does not appear, every name is kept and the queue comes out the same. Remember that remove would raise ValueError.
• The last line shows that neither function has changed queue: both return new lists.

Level 3 solution

linked.py

def from_list(items):
    """Turns a Python list into a linked queue (name, rest)."""
    if items == []:
        return ()
    return (items[0], from_list(items[1:]))


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


def to_text(queue):
    """Returns the queue as 'Ana -> Luis -> Marta'."""
    if queue == ():
        return "(empty)"
    name, rest = queue
    if rest == ():
        return name
    return name + " -> " + to_text(rest)


def cut_in(queue, name, in_front_of):
    """Returns a new queue with name right in front of in_front_of.
    If in_front_of is not there, name goes at the end."""
    if queue == ():
        return (name, ())
    first, rest = queue
    if first == in_front_of:
        return (name, queue)
    return (first, cut_in(rest, name, in_front_of))


queue = from_list(["Ana", "Luis", "Marta"])
print(queue)
print(length(queue), "people:", to_text(queue))
new_queue = cut_in(queue, "Pablo", "Marta")
print(to_text(new_queue))
print(to_text(cut_in(queue, "Sara", "Lucía")))
print(to_text(queue))
print(to_text(()))

Why it is done this way:

• from_list builds the queue from the front to the back with recursion: the first node stores the first name and, as its rest, the linked queue of the rest of the list. The base case turns the empty list into the empty queue ().
• length unpacks each node with name, rest = queue and adds 1 per node. name is not used, but unpacking like this makes it clear what each part is.
• to_text has two base cases: the empty queue (which only happens if the whole queue is empty) and the last node, whose rest is (). Thanks to that second case, there is no arrow after Marta.
• cut_in is the most interesting one. If the first node is in_front_of, it returns (name, queue): a new node pointing to the usual queue. If not, it returns (first, cut_in(rest, …)): it rebuilds the first node with the rest already changed. Since tuples are immutable, you cannot “hook” Pablo into the original queue; you have to create new nodes up to the insertion point.
• If it reaches the empty queue without finding in_front_of, the base case returns (name, ()): a last node with name. That is why Sara ends up at the end.
• The original queue does not change: to_text(queue) still shows Ana, Luis and Marta. Besides, the new queue shares Marta’s node with the original one: new nodes are only created for Ana, Luis and Pablo.

Watch it step by step in Python Tutor

The bug in snippet 3 is much easier to understand live. Python Tutor runs the code line by line and shows the value each call returns. Choose Python 3 and paste this program, which looks for Marta with the broken version and with the good one:

def is_in(queue, name):
    if queue == []:
        return False
    if queue[0] == name:
        return True
    is_in(queue[1:], name)


def is_in_fixed(queue, name):
    if queue == []:
        return False
    if queue[0] == name:
        return True
    return is_in_fixed(queue[1:], name)


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

Expected output:

None
True

What to watch, step by step:

1. In is_in(queue, "Marta") three frames pile up: the queue with three names, with two and with one. In the third, queue[0] is "Marta" and Python Tutor shows Return value: True.
2. Now look at the second frame on the way back: the line is_in(queue[1:], name) has finished, but its True is not stored anywhere. The function reaches the end and its return value is None.
3. The first frame does the same: it receives None and returns None. That is what the first print shows.
4. Repeat with is_in_fixed: in the second and the first frame, the return value is True, because the return passes the answer up from one frame to the next.
5. Compare both runs: the frames and the arguments are identical. The only difference is whether the answer travels up or gets lost, and a return decides that.

Cheat sheet: Recursion

The essentials in 30 seconds

• A recursive function calls itself with a smaller version of the problem.
• Base case: the smallest input, answered without calls. General case: combines the first step with the call on the rest.
• The call has to reduce the problem (items[1:], n - 1, n // 2, low/high getting closer).
• Every path returns something: return in front of the recursive call.
• Calls pile up: what comes before the call runs on the way down; what comes after, on the way back. Limit: about 1000.
• Do not repeat identical calls: store the result in a variable.
• Immersion: add parameters (position, zone, accumulator) in a helper function and call it from the original one.

Syntax

I want to…	Code	Result
Basic pattern	if base_case: return value / return combine(x, f(rest))	Recursive function
First and rest	items[0] and items[1:]	The rest is a shorter list
Rest and last	items[:-1] and items[-1]	The same, but from the end
Add up a list	return items[0] + add(items[1:])	Base case: 0
Count with a condition	return (1 if cond else 0) + count(items[1:])	Base case: 0
Search	if items[0] == x: return True / return is_in(items[1:], x)	Base case: False
Build a list	return [items[0]] + f(items[1:])	New list
Reverse	return reverse_queue(items[1:]) + [items[0]]	List backwards
Binary search	mid = (low + high) // 2 and call with (low, mid) or (mid + 1, high)	Position or -1
Immersion	def f(items): return f_from(items, 0)	Simple interface, no copies
Linked node	name, rest = queue	Base case: queue == ()
Detect a sublist	isinstance(x, list)	True if x is a list
See the limit	sys.getrecursionlimit()	1000

Templates from the exercises

Going through a list with first and rest (Level 1):

def total(prices):
    if prices == []:
        return 0
    return prices[0] + total(prices[1:])

Building a new filtered list (Level 2):

def remove_person(queue, name):
    if queue == []:
        return []
    if queue[0] == name:
        return remove_person(queue[1:], name)
    return [queue[0]] + remove_person(queue[1:], name)

Reversing (Level 2):

def reverse_queue(queue):
    if queue == []:
        return []
    return reverse_queue(queue[1:]) + [queue[0]]

Linked list: going through and rebuilding (Level 3):

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


def cut_in(queue, name, in_front_of):
    if queue == ():
        return (name, ())
    first, rest = queue
    if first == in_front_of:
        return (name, queue)
    return (first, cut_in(rest, name, in_front_of))

Binary search by immersion (theory and practice):

def search_range(items, x, low, high):
    if low >= high:
        return -1
    mid = (low + high) // 2
    if items[mid] == x:
        return mid
    if items[mid] > x:
        return search_range(items, x, low, mid)
    return search_range(items, x, mid + 1, high)

The most common bugs

Symptom	Likely cause
RecursionError: maximum recursion depth exceeded	There is no base case, it is never reached or the call does not reduce the problem (items[0:], n instead of n - 1)
RecursionError with a correct function	The input is too large for about 1000 calls: look for a less deep solution or use a loop
The function returns None	A return is missing in front of the recursive call
The result is always 1 too many (or too few)	The base case returns a wrong value (return 1 instead of return 0)
TypeError: can only concatenate list (not "str") to list	You concatenate a single element: put it in brackets, [x]
The binary search never ends	You call with mid instead of mid + 1 in the right half
The position found is not the one in the original list	You search with slices: use immersion with low and high
ValueError: not enough values to unpack in a linked list	You unpack (): check the base case queue == () first
The function is extremely slow with large numbers	You repeat the same recursive call: store the result in a variable

Before you hand it in, ask yourself

1. What is my base case, and does it return the correct answer for the smallest input?
2. Does every recursive call receive something smaller than the previous one?
3. Does every path of the function end in a return (if the function must return something)?
4. Do I make the same recursive call more than once, or copy the list on every call when I could use indexes?

If you want to review the topic from the basics, go back to the recursion theory.

Keep goingAll Python (en) articles

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