Recursion Explained Using Sandwiches

• If you put a piece of toast between two slices of bread, you have a toast sandwich.
• If you put a piece of bread between two slices of bread, you have a bread sandwich.
• If you put a piece of bread between two pieces of toast you have a toasted bread sandwich.

It would be nice to have a program that identifies what sort of sandwich we have.

If we’re going to do this we’ll need a way to represent the make up of our sandwich. One way would be to use lists, as follows

• [B,T,B] Toast sandwich
• [B,B,B] Bread sandwich
• [T,B,T] Toasted bread sandwich

We can now represent more complicated sandwiches such as the following:

• [B,T,B,T,B] Toasted bread sandwich sandwich
• [T,T,B,T,T] Toasted toasted bread sandwich sandwich

Now we have a sandwich data structure, we can write a program that will accept a list such as [B,T,B] as input and then output “Toast sandwich”.

… but before we start reaching for a for loop to traverse that list, let’s just to a moment to notice something. Sandwiches have sandwiches inside them.

If you look at [B,T,B,T,B], a toasted bread sandwich sandwich, you’ll notice that it’s really just a [T,B,T] or toasted bread sandwich wrapped in bread. And in fact, a [T,B,T] is just a piece of bread wrapped in toast.

Let’s do the above backwards

• [B] – A piece of bread
• [T,B,T] – A toasted bread sandwich
• [B,T,B,T,B] – A toasted bread sandwich wrapped in bread, in other words, a toasted bread sandwich sandwich

To check you’ve understood this, try deconstructing a [T,B,T,B,T,B,T]. You should get a toasted toasted bread sandwich sandwich sandwich.

The fact that we can repeatedly reduce this problem to simpler sandwich, two slices at a time, tells us that this problem could be solved by recursion. We’re going to write a recursive function that strips away the sandwich, two slices at a time.

Start by defining a function called SNS (sandwich name service). This function will use python slicing to find the base, top and filling of the sandwich.

If the sandwich contains only one item it will simply be a piece of bread or a piece of toast. A one item sandwich will be the base case or escape clause for our recursive function.

If the sandwich contains more than one item, we’ll remove the outer layers and then call the SNS function again with the filling.

Here are a couple of examples

Input [T]

This is a one item sandwich, so SNS outputs “toast”

Input [B,B,T,B,B]

This is not a one item sandwich, so SNS strips the outer bread layers and then calls itself with the filling:

SNS([B,T,B]) + “sandwich”

Here’s the code:

B = "bread"
T = "toast"

def SNS(sandwich):
    base = sandwich[0]
    top = sandwich[-1]
    filling = sandwich[1:-1]

    if len(sandwich) == 1:
       return sandwich[0]
    if base == top:
       if base == B:
          return SNS(filling) + " sandwich"
    else:
          return "toasted " + SNS(filling) + " sandwich"


print(SNS([T,B,B,B,T]))

And there we have it. Sandwiches identified recursively.

There are problems with this code. It doesn’t check for incorrect input. It doesn’t identify even numbered lists correctly as open faced sandwiches or things on toast. Perhaps you could fix that…