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

I wanted to know at which position of the list my canteen ticket number, 58, was, so I wrote a recursive binary search with slices: look at the middle one and, if it is not the one, keep searching the right half with tickets[mid + 1:] or tickets[:mid]. When it found it, it returned mid. The function found 58 without any trouble… and told me it was at position 0. In a list of 16 sorted tickets, 58 was at position 11.

It took me a while to see it: each slice is a new list, and its positions start at 0 again. When the function found 58, it found it in a little piece with a single element, and position 0 of that piece had nothing to do with the original list. The fix is the immersion technique from the theory: do not cut the list and carry the indexes as parameters.

Today we practise recursion with three complete programs: the canteen queue accounts, a ticket search that prints every call on screen and a group order with sub-orders inside sub-orders. This practice builds on the recursion theory. If you still hesitate with slices or with lists of lists, review mutability, copies and matrices first.

How to use this article

Each program is complete in a single file. Copy it, save it with the name shown and launch it from the terminal with python3 name.py. Before looking at the output, try to predict it: in recursion, predicting what each call returns is exactly the skill you need to train.

Program 1 · The canteen queue accounts

The queue is a list of tuples (name, menu, price). We want four things, all with recursive functions: how much is charged in total, how many menus of a kind there are, which tray is the most expensive and at which position a person is.

canteen.py

QUEUE = [
    ("Ana", "normal", 5.50),
    ("Luis", "vegetarian", 5.00),
    ("Marta", "normal", 5.50),
    ("Pablo", "vegetarian", 5.00),
    ("Sara", "dessert", 2.25),
]


def total(queue):
    """Adds up what the whole queue pays."""
    if queue == []:
        return 0
    name, menu, price = queue[0]
    return price + total(queue[1:])


def count_menu(queue, kind):
    """Counts the trays of one kind of menu."""
    if queue == []:
        return 0
    name, menu, price = queue[0]
    if menu == kind:
        return 1 + count_menu(queue[1:], kind)
    return count_menu(queue[1:], kind)


def most_expensive(queue):
    """Returns the most expensive tray (the queue cannot be empty)."""
    if len(queue) == 1:                    # base case: a single tray
        return queue[0]
    best_of_rest = most_expensive(queue[1:])
    if queue[0][2] >= best_of_rest[2]:
        return queue[0]
    return best_of_rest


def position(queue, name, pos=0):
    """Position of name in the queue, or -1 if not there."""
    if pos == len(queue):                  # we have looked at everyone
        return -1
    if queue[pos][0] == name:
        return pos
    return position(queue, name, pos + 1)


print(f"Total to charge: {total(QUEUE):.2f} €")
print("Vegetarian menus:", count_menu(QUEUE, "vegetarian"))
print("Most expensive tray:", most_expensive(QUEUE))
print("Pablo is at position", position(QUEUE, "Pablo"))
print("Lucía is at position", position(QUEUE, "Lucía"))

Launch it with python3 canteen.py:

Total to charge: 23.25 €
Vegetarian menus: 2
Most expensive tray: ('Ana', 'normal', 5.5)
Pablo is at position 3
Lucía is at position -1

Between the lines:

• total and count_menu follow the first and rest pattern: they unpack the first tuple with name, menu, price = queue[0] and call with queue[1:]. The base case, the empty queue, returns 0 in both. The numbers add up: 5.50 + 5.00 + 5.50 + 5.00 + 2.25 = 23.25.
• most_expensive has a different base case: a single tray. Why not the empty queue? Because an empty queue has no most expensive tray: there is nothing reasonable to return. That is why the docstring warns that the queue cannot be empty.
• In the general case of most_expensive, the most expensive tray of the rest is computed first and then compared with the first one. Ana and Marta pay the same (5.50) and Ana wins because the comparison is >=: in case of a tie, the first one stays. With > you would have got Marta.
• position uses immersion: instead of cutting the queue, it carries a pos parameter that starts at 0 (default value) and moves forward one by one. That way it does not copy the list and, when it finds Pablo, pos is his real position (3). If it reaches the end without finding someone, it returns -1, as with Lucía.

Try it yourself

• Change >= to > in most_expensive and check that you now get Marta. Then explain in your own words why.
• Write cheapest(queue) following the same pattern as most_expensive. Which tray should come out?
• Rewrite total with immersion, with a pos=0 parameter instead of queue[1:]. What is the base case now?

Program 2 · Searching a ticket, call by call

In the canteen we hand out ticket numbers, and the list of tickets still waiting is sorted. We look for a ticket with binary search and print every call to see how the zone narrows down.

tickets.py

TICKETS = [3, 8, 12, 15, 21, 27, 30, 34, 41, 47, 52, 58, 63, 70, 76, 81]


def search(tickets, ticket, low, high, call=1):
    """Looks for ticket between positions low and high - 1."""
    if low >= high:
        print(f"  Call {call}: empty zone, not there")
        return -1
    mid = (low + high) // 2
    print(f"  Call {call}: I look from {low} to {high - 1}, in the middle there is {tickets[mid]}")
    if tickets[mid] == ticket:
        return mid
    if tickets[mid] > ticket:
        return search(tickets, ticket, low, mid, call + 1)
    return search(tickets, ticket, mid + 1, high, call + 1)


def find_ticket(tickets, ticket):
    return search(tickets, ticket, 0, len(tickets))


for ticket in [58, 3, 50]:
    print(f"Looking for ticket {ticket}")
    print("  Position:", find_ticket(TICKETS, ticket))

Launch it with python3 tickets.py:

Looking for ticket 58
  Call 1: I look from 0 to 15, in the middle there is 41
  Call 2: I look from 9 to 15, in the middle there is 63
  Call 3: I look from 9 to 11, in the middle there is 52
  Call 4: I look from 11 to 11, in the middle there is 58
  Position: 11
Looking for ticket 3
  Call 1: I look from 0 to 15, in the middle there is 41
  Call 2: I look from 0 to 7, in the middle there is 21
  Call 3: I look from 0 to 3, in the middle there is 12
  Call 4: I look from 0 to 1, in the middle there is 8
  Call 5: I look from 0 to 0, in the middle there is 3
  Position: 0
Looking for ticket 50
  Call 1: I look from 0 to 15, in the middle there is 41
  Call 2: I look from 9 to 15, in the middle there is 63
  Call 3: I look from 9 to 11, in the middle there is 52
  Call 4: I look from 9 to 9, in the middle there is 47
  Call 5: empty zone, not there
  Position: -1

Between the lines:

• search works with the whole list and two indexes: low (included) and high (excluded). It is the immersion search from the theory, with an extra parameter, call, that only serves to number the lines of the trace.
• Follow ticket 58: the first call looks from 0 to 15 and finds 41 in the middle. Since 58 is greater, the ticket can only be on the right: the second call looks from 9 to 15. There the middle is 63, greater than 58, so it goes left (from 9 to 11). In the fourth call, the zone has a single ticket and it is 58: position 11, the real position in TICKETS.
• Ticket 3 is at the start and needs one more call (5), because the zone always keeps the left half until it has a single element.
• Ticket 50 does not exist. After four calls, the zone from 9 to 9 holds 47; since 50 is greater, the next zone would go from 10 to 9, that is, low >= high: empty zone, and the function returns -1.
• With 16 tickets, no search needs more than 5 calls. With a linear search, finding 81 would have needed 16. With a million tickets, binary search would make about 21 calls; the linear one, up to a million (and it would not fit in Python’s stack).
• find_ticket is the wrapper: whoever uses it only passes the list and the ticket, without worrying about low, high or call.

Try it yourself

• Search for ticket 81 (the last one) and 20 (it does not exist). Before running, predict how many calls each search will make.
• Change mid + 1 to mid and search for 50. Watch in the trace how the zone stops shrinking.
• Write the version with slices (no low or high) that returns mid, search for 58 and check that it gives you a wrong position. That way you will see the bug from the beginning with your own eyes.

Program 3 · A group order with sub-orders

To finish, a structure that screams for recursion. The lab group places a joint order: some people order a single thing (a price) and others order several things (a list of prices). And inside the group’s table, someone again orders several things. It is a list that can contain lists, at any depth.

orders.py

ORDER = [
    5.50,                       # Ana: set menu
    [5.00, 2.25],               # Luis: set menu and dessert
    [                           # lab group table
        5.50,
        [5.00, 1.50],           # Pablo: set menu and coffee
        5.50,
    ],
    2.25,                       # Sara: dessert
]


def total(order):
    """Adds up all the prices, whatever level they are at."""
    if order == []:
        return 0
    first = order[0]
    if isinstance(first, list):           # the first one is a sub-order
        return total(first) + total(order[1:])
    return first + total(order[1:])


def count_dishes(order):
    """Counts the single prices (the dishes)."""
    if order == []:
        return 0
    first = order[0]
    if isinstance(first, list):
        return count_dishes(first) + count_dishes(order[1:])
    return 1 + count_dishes(order[1:])


def flatten(order):
    """Returns a list with all the prices, not nested."""
    if order == []:
        return []
    first = order[0]
    if isinstance(first, list):
        return flatten(first) + flatten(order[1:])
    return [first] + flatten(order[1:])


def levels(order):
    """How many levels of lists there are, counting the outer one."""
    maximum = 1
    for element in order:
        if isinstance(element, list):
            maximum = max(maximum, 1 + levels(element))
    return maximum


print(f"Total: {total(ORDER):.2f} €")
print("Dishes:", count_dishes(ORDER))
print("Flat list:", flatten(ORDER))
print("Levels:", levels(ORDER))

Launch it with python3 orders.py:

Total: 32.50 €
Dishes: 8
Flat list: [5.5, 5.0, 2.25, 5.5, 5.0, 1.5, 5.5, 2.25]
Levels: 3

Between the lines:

• total, count_dishes and flatten have the same structure: base case with the empty list and, in the general case, two situations depending on what the first element is. If it is a number, it is combined directly with the rest. If it is a list, isinstance(first, list) detects it and one recursive call is made for the sub-order and another one for the rest.
• This is new compared to the queue: here each call can make two recursive calls, one that goes “down” into the sublist and another one that goes “forward” through the list. That is why it works with any level of nesting without writing one loop per level.
• The numbers add up: 5.50 + (5.00 + 2.25) + (5.50 + (5.00 + 1.50) + 5.50) + 2.25 = 32.50, and there are 8 single prices, which are exactly the ones in the flat list.
• flatten builds a new list by concatenating with +: flatten(first) + flatten(order[1:]) joins the prices of the sub-order with those of the rest, and [first] + … puts a single number inside a list so it can be concatenated.
• levels mixes a loop and recursion: it goes through the elements with a for and, for each sublist, asks how many levels it has. The order has 3: the outer list, the group’s table and Pablo’s order inside the table.

Try it yourself

• Add an empty list, [], at the end of the order. Does the total change? And the levels? Run it and check whether you were right.
• Write most_expensive(order) that returns the highest price in the whole order, whatever level it is at. Hint: you can reuse flatten, or write it with the same pattern as total.
• Put Pablo’s order one level deeper ([[5.00, 1.50]]) and predict what changes in each line of the output.

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. Choose Python 3 and paste this binary search by immersion, which looks for a ticket that is there and one that is not:

def search(tickets, ticket, low, high):
    if low >= high:
        return -1
    mid = (low + high) // 2
    if tickets[mid] == ticket:
        return mid
    if tickets[mid] > ticket:
        return search(tickets, ticket, low, mid)
    return search(tickets, ticket, mid + 1, high)


tickets = [3, 8, 12, 15, 21, 27, 30]
print(search(tickets, 21, 0, len(tickets)))
print(search(tickets, 10, 0, len(tickets)))

Expected output:

4
-1

What to watch, step by step:

1. In the first call, the search frame has low = 0 and high = 7, and mid is 3 (ticket 15). Since 21 is greater, a second frame is created with low = 4.
2. Look at the tickets arrow in every frame: it always points to the same list. Immersion copies nothing; only low and high change.
3. In the second frame, mid is 5 (ticket 27). Since 27 is greater than 21, the third frame has high = 5. There mid is 4, ticket 21: the function returns 4, and that value travels up untouched through all the frames to the print.
4. In the second search (ticket 10), watch how the zone shrinks until low and high become equal. In that frame low >= high is met and the return value is -1.
5. Notice that no frame does anything on the way back: each one directly returns what the next one answers. That is why the result of the last one reaches the first one as it is.

To finish

Today you have seen recursion in three different situations: going through a list with first and rest (and with immersion, so as not to copy it), splitting the problem in half with a binary search that shows its own stack, and going through a nested structure where every element can be another list. If something did not click, go back to the theory; and when you feel comfortable, move on to the exercises, where the bugs come included.

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

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