Coding Comics: Recursion

What Is This?

This is a re-working of the Coding Strip Recursion example. Not because I can do it better, but because I've never done one before so stealing their idea seems like an easier way to start. In the original they had a comic showing a character who wants to buy a ticket but there's a long line so she asks the person in front of her how many people are in front of him, and he asks the person in front of him, and so on. They then followed up the comics with some code that translated the comic to a concrete function.

The Comic

(Coming Soon)

In English-Ish


To find the length of the line, each person asks the person in front how many people are in front of them.

Base Case

When the person at the front of the line is reached, he reports that there's no one in front of him (zero).


Once the front of the line is reached, each person then relays back how many people the person in front reports and adds one to include the person who reported the count until the back of the line is reached.

The Code

Here's some code to illustrate the idea of asking the person in front of you how many people are in front of them and having that question propagate forward and then have the answer propagate back.

A Person

I originally thought of using a list, but then you'd have to criple the length method… so I'm making a linked list of a sorts, where each person knows the person in front of them.

class Person:
    """A person in line
    person_in_front = None

The Recursion

def hey_fella_how_many_people_are_in_front_of_me(fella: Person):
    """Finds out how many people are in front of current person

     fella: the current person being asked

     Number of people in front (including last person)
    COUNT_THIS_FELLA = 1    
    if fella.person_in_front is None:
        return COUNT_THIS_FELLA
    return (hey_fella_how_many_people_are_in_front_of_me(fella.person_in_front)
            + COUNT_THIS_FELLA)

Check If It Works

Now I'll create a line of unknown length so we can check it.

from string import ascii_letters
import random

waiting = random.randrange(1, 1000)

def line_of_people(people: int) -> Person:
    """Builds the lengthless line

     people: how many people to queue up

     line of people
    line = this_person = Person()
    for person in range(1, waiting):
        this_person.person_in_front = Person()
        this_person = this_person.person_in_front
    return line

in_line = line_of_people(waiting)

So at this point we have a line of people of unknown length. Each person only knows the existence of the person in front of them so there's no way to get the length of the line directly, but we can use the recursive function to find out how many people there are.

reported = hey_fella_how_many_people_are_in_front_of_me(in_line)
print(f"Expected: {waiting}, Actual: {reported}")

assert waiting == reported
Expected: 539, Actual: 539

Seems to be working.