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…

Coin Change Problem

Famously (or at least famously in maths puzzle circles) there are 293 ways to make a US dollar using the following coins:

Penny (1 cent) | Nickel (5 cents) | Dime (10 cents) | Quarter (25 cents) | Half Dollar (50 cents) | Dollar (100 cents)

You could make a dollar with, for example, 4 quarters or 10 dimes.

How many ways are there of making a Brtish pound?

At the time of writing GB currency has the following coins

1p, 2p, 5p, 10p, 20p, 50p and £1 or 100p.

It’s usually a good idea to start problems like this by looking at simpler cases.

If we only have 1p coins, the answer is easy. There’s only 1 way to make any value: 1p = 1, 2p = 1 + 1, 3p = 1 + 1 + 1 etc

How about if we have 1p and 2p coins?

ValuePossibleWays
1p1p1
2p2 x 1p, 2p2
3p3 x 1p, 2p + 1p2
4p4 x 1p, 2p + 2p, 2p + 1p + 1p3
5p5 x 1p, 2 x 2p +1p, 2p + 3 x 1p3

Extend the table and you quickly see a pattern

ValueWays
1p1
2p2
3p2
4p3
5p3
6p4
7p4
8p5
9p5
10p6

We could write the following python code to work out the number of ways of making values with only 1 or 2p coins:

def coin12(n):
if n%2 == 0:
return int(n/2 +1)
else:
return int((n + 1)/2)

What about if we have 1p, 2p and 5p coins?

It turns out we can use our previous function to help us work this out.

For example, we could make 8p entirely of 2s and 1s. But this is just coin12(8) ways using the above function

We could make 8p using a 5p coin and 3p made of 2s and 1s: this is coin12(3) ways

This lets us write out the following table.

ValuePossibleWays
1pcoin12(1)1
2pcoin12(2)2
3pcoin12(3)2
4pcoin12(4)3
5p5p, coin12(5)4
6p5p + 1p, coin12(6)5
7p5p + coin12(2), coin12(7)6
8p5p + coin12(3), coin12(8)7
9p5p + coin12(4), coin12(9)8
10p5p + 5p, 5p + coin12(5), coin12(10)10

We can use this to help us write a new function

def coin125(n):
total =0
while n >= 5:
total += coin12(n)
n -= 5
return total + coin12(n)

When the function is tested, the results match the table above.

for i in range (1,11):
print(i ,": " ,coin125(i))

Now we can look at using the 1p, 2p, 5p and 10p coins. Our coin125 function suggests a way this can be done:

def coin12510(n):
total =0
while n >= 10:
total += coin125(n)
n -= 10
return total + coin125(n)

Similarly we could make functions for coins up to 20p, 50p and 100p

I’ve missed out some of the steps below, but working through all the coins I finished up with the following function:

 def coin125102050100(n):
total =0
while n >= 100:
total += coin125102050(n)
n -= 100
return total + coin125102050(n)
print(coin125102050100(100))

Which gave me the correct answer: 4563. In other words, there are 4,563 ways to make £1 using 1p, 2p, 5p, 10p, 20p, 50p and £1 coins.

However.

This isn’t very elegant. Looking at the code we can see we’re doing the same thing over and over again. Also, what if we had a currency that used 100 coins? Or 1000? It would take a lot of copying and pasting to work those problems out.

There has to be a better way.

Let’s look at the functions again. It’s easy to spot a pattern to them. Using pseudocode, they can be written out something like this:

define coinVALUES(n):
total =0
while n >= VALUE:
total += coinVALUES-1(n)
n -= VALUE
end while
return total + coinVALUES-1(n)
end define

Here’s a first attempt at writing the above in Python

values = [100, 50, 20, 10, 5, 2, 1]
def coin(n, val):
total = 0
while n> values[val]:
total += coin(n, val+1)
n -= values[val]
return total + coin(n, val+1)

You might notice I’ve written a recursive function, but there’s a problem. There’s no escape clause, there’s nothing to stop the function calling itself forever.

That’s quite easy to fix though

All we have to do is realise that coin1(n) = 1. If you want to make 5p using only 1p coins, there’s only one way to do it: 1p + 1p + 1p + 1p + 1p.

We can use that to add a clause to make a proper recursive function.
It also sorts out an irritating niggle: why should coin12 be different to all the other coin functions?

values = [100, 50, 20, 10, 5, 2, 1]
def coin(n, val):
if values[val] == 1:
return 1
total = 0
while n>= values[val]:
total += coin(n, val+1)
n -= values[val]
return total + coin(n, val+1)
print(coin(100,0))

This works but it’s a little bit messy. I have to call the function with an extra argument, 0, telling it to start at the beginning of the values list.

It would be better to treat coin as a “helper” function and to write another function to call it. This would make the function a lot more user friendly.

I’ve wrapped the coin function in a one called makechange. To show the flexibility of my function, I’ve used makechange to work out how many ways there are to make change from a dollar.

 values = [100, 50, 25, 10, 5, 1]

def coin(n, val):
if values[val] == 1:
return 1
total = 0
while n>= values[val]:
total += coin(n, val+1)
n -= values[val]
return total + coin(n, val+1)

def makechange(n):
return coin(n,0)

print(makechange(100))

The Best Programming Language

As Andrew Hunt and David Thomas say in the Pragmatic Programmer, there’s no such thing as the best programming language, just the best programming language for the job in hand.

However, if I had to choose the best language it would be Lisp. Here’s why:

The following code is written in Emacs Lisp. It prints out all the elements of a list

(cl-loop for element in mylist do (print element))

In the code below I’ve set mylist to equal the numbers one to five. Evaluating the loop will, unsurprisingly, print the numbers one to five.

(setq mylist '(1 2 3 4 5))
(cl-loop for element in mylist do (print element))
=> 1
2
3
4
5

You’re probably thinking you can do the same in Python or Java or whatever your preferred language is, and you’d be right.

But can your preferred language do this?

(setq mylist '(cl-loop for element in mylist do (print element)))
mylist
=> (cl-loop for element in mylist do (print element))

In the above code I’ve set mylist to be the loop itself.
That means I can set the loop code to loop across itself and print itself out one word at a time.

 (cl-loop for element in mylist do (print element))
=> cl-oop
for
element
in
... etc

In Lisp, code is data. So mylist is data; it’s a list of symbols: cl-loop for element etc. But I can also evaluate mylist in which case mylist will be a set of instructions to loop across itself and print itself out.

(eval mylist) 
=> cl-oop
for
element
in
... etc

Or to put it another way, I’ve just written a list that can read itself!

The thing that makes this possible is the fact that Lisp is a homoiconic language: programs written in such a language can be manipulated as data using the language.

Things like this give me a warm glow inside. They remind me why I love coding so much.

Writing Better Code 1

The number 28 has 6 divisors:

1,2,4,7,14,28

The number 5 only has 2 divisors:

1,5

Write a program to find all the divisors of a number.

The mod operator is useful here. Remember that the mod operator gives the remainder when two numbers are divided, so

28 % 14 = 0 
28 % 5  = 3

We can use the mod function to write code as follows

def divisors(n):
    divs = []
    for i in range(1,n+1):
    if n%i == 0:
        divs.append(i)
    return divs

print(divisors(28))

The above code is inefficient. To find the divisors of 28, you have to go through the for loop 28 times. To find the divisors of n, we have to go through the for loop n times. We say the code has time complexity O(n).

Try running the code to find the divisors of a large number such as 1347663998. You’ll notice it takes a long time to find the answer. We need a way to make the code more efficient.

You should notice that the divisors come in pairs. (1,28, 2,14 4,7). This suggests a way of saving loops. Rather than looking at all the numbers, we could look at just half of them.

import math

def divisors(n):
    divs = []
    for i in range(1,int(n/2)):
    if n%i == 0:
        divs.append(i)
        divs.append(int(n/i))
    return divs

print(divisors(28))

That seems better, but testing we get repeated divisors

[1, 28, 2, 14, 4, 7, 7, 4]

Thinking about it further we see that we only need to count as far as the square root of n (because root n * root n = n)

import math

def divisors(n):
    divs = []
    for i in range(1,int(math.sqrt(n))):
    if n%i == 0:
        divs.append(i)
        divs.append(int(n/i))
    return divs

print(divisors(28))

There’s still a problem though.

What about divisors of 9?

Run the above code with divisors(9) and you just get

[1, 9]

Isn’t 3 a divisor of 9? The problem lies in our range. We’re counting up to one less then root 9. Let’s tweak the code to take this case into account.

import math

def divisors(n):
    divs = []
    for i in range(1, int(math.sqrt(n))):
    if n%i == 0:
        divs.append(i)
        divs.append(int(n/i))
    if math.sqrt(n).is_integer():
        divs.append(int(math.sqrt(n)))
    return divs

print(divisors(9))

We’ve now got working code that runs a lot faster than the original code.

There are a couple of further tweaks we can make. 

Firstly, all numbers are divisible by 1 and themselves, so we can just append them without checking.

Odd numbers are never divisible by even numbers.  So, if n is odd, we only need to check if n is divisible by 3, 5, 7 …

If n is even we need to check all numbers from 2 onwards.

import math

def divisors(n):
divs = []
step = 1
start = 2
if n%2 == 1:
step = 2
start = 3
for i in range(start, int(math.sqrt(n)), step):
if n%i == 0:
divs.append(i)
divs.append(int(n/i))
if math.sqrt(n).is_integer():
divs.append(int(math.sqrt(n)))
divs.append(1)
divs.append(n)
return divs

One last thing. In the new code the following calculation appears three times: math.sqrt(n)

It takes the computer a lot longer to work out square roots than to do other calculations. Now, a good compiler should notice this. It will perform optimisation on your code and will store repeated calculations to stop them having to be worked out over and over again.

However, it might be more elegant to adjust your code as follows.  I’ve also added a line to sort the divisors into order.

import math

def divisors(n):
divs = []
rootn = math.sqrt(n)
step = 1
start = 2
if n%2 == 1:
step = 2
start = 3
for i in range(start, int(rootn), step):
if n%i == 0:
divs.append(i)
divs.append(int(n/i))
if rootn.is_integer():
divs.append(int(rootn))
divs.append(1)
divs.append(n)
divs.sort()
return divs