Recursion: Nature's Cheat Code
In his famous 1979 book Gödel, Escher, Bach: An Eternal Golden Braid, Douglas Hofstadter coined "Hofstadter's Law" to describe when computers would best humans in chess:
Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law. Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid
The statement is an instance of recursion, where an object contains a reference to itself. Throughout G.E.B., Hofstadter outlines a theory in which consciousness is the inevitable result of "strange loops"—or complex, hierarchical, recursive structures—happening within our own brains.
Recursion can clearly have humorous qualities. A hidden punchline, for instance. In a nod to Hofstadter, Randall Munroe of XKCD created:
I'm So Meta, Even This Acronym
The powerful nature of recursion has been known to mathematicians for hundreds of years. Take for example the equation:
$f_n = f_{n-1} + f_{n-2}$
If we let $f_0 = 1$ and $f_1 = 1$, this equation renders the Fibonacci sequence, a mathematical concept that has fascinated artists, scientists and mathematicians for ages, and which is found over and over again in nature.
$f_0 = 1$
$f_1 = 1$
$f_2 = f_0 + f_1 = 1 + 1 = 2$
$f_3 = f_1 + f_2 = 1 + 2 = 3$
$f_4 = f_2 + f_3 = 2 + 3 = 5$
The beauty of recursive structures lies in the disconnect between their simplicity and their extraordinary power. Take for instance the Mandelbrot set, a manifestation of a simple recursive equation:
$z_{n+1} = z_n^2 + c$
It seems easy enough for Fibonacci, but things can quickly get out of hand when trying to construct a recursive algorithm. In computer science education, programmers are taught not only to understand recursion, but also to "trust" it. Attempting to trace the logic down more than a couple levels will lead ultimately to madness. Our job as programmers is simply to set up the scaffolding, and trust that if it works for simple input, then it should work for more complex input.
Let's try an example from Project Euler.
The Problem
In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?
Plan of Attack
How would you go about solving this problem without a computer? Most of the time, if you can think of a systematic way of doing it manually, you can make the computer do it for you.
To make the problem more managable, let's see if we can make something work with just three coins: 200p (2£), 100p (1£), and 50p.
Recursion is not just an abstract concept; we use it naturally all the time in problem solving. In fact, one of the most natural ways of solving this problem is actually recursive. I set it up here with nested lists to show the logic visually. We'll work our way down from the highest value coin (200p) to the lowest (50p).
Imagine you have a bowl of coins in front of you.
- Take a 200
- Subtotal (200) = 200
- Add 1 to combos (0+1=1), go back
- Take a 100
- Subtotal (100) < 200
- Take a 100
- Subtotal (200) = 200
- Add 1 to combos (1+1=2), go back
- Take a 50
- Subtotal (150) < 200
- Take a 50
- Subtotal (200) < 200
- Add 1 to combos (2+1=3), go back
- No more smaller coins, go back
- No more smaller coins, go back
- Take a 50
- Subtotal (50) < 200
- Take a 50
- Subtotal (100) < 200
- Take a 50
- Subtotal (150) < 200
- Take a 50
- Subtotal (200) = 200
- Add 1 to combos (3+1=4), go back
- No more smaller coins, go back
- No more smaller coins, go back
- No more smaller coins, go back
- No more smaller coins
- Total = 4
Notice how at each level of depth, we are applying the exact same rules as the level above it. That is recursion!
The Solution
Though we'll be going through it step by step in this post, the truth is that programming is never a straightforward task. You will be jumping from one section of code to the other. Getting everything to work together requires a lot of tinkering, and tinkering takes time.
So here is the complete javascript program we're building. Take a look and see if you can understand how it all works together.
var coins = [200,100,50,20,10,5,2,1],
target = 200,
combos = 0;
function add_coin(coin,subtotal) {
var sub_combos = 0;
subtotal += coins[coin];
if (subtotal > target) return 0;
if (subtotal === target) return 1;
for (var c = coin; c < coins.length; c++) {
sub_combos += add_coin(c,subtotal);
}
return sub_combos;
}
for (var c = 0; c < coins.length; c++) {
combos += add_coin(c,0);
}
console.log(combos);
Breaking It Down
First we'll set up an array of coins, the target value (200p) and a variable to hold the number of combinations we end up with.
var coins = [200,100,50,20,10,5,2,1],
target = 200,
combos = 0;
We start by choosing each starting coin in succession, from highest value to lowest. We then call the function add_coin(), which returns the number of sub-combinations using each starting coin and add that value to combos. We have to send the function two parameters: (1) the current coin, and (2) the current subtotal. Since we are adding the first coin, the subtotal is 0.
for (var c = 0; c < coins.length; c++) {
combos += add_coin(c,0);
}
Next, we'll set up a function which will systematically add coins one at a time, and eventually return the number of sub-combinations for that starting coin.
function add_coin(coin,subtotal) {
var sub_combos = 0;
subtotal += coins[coin];
// check the subtotal against the target
// return 0 if we go over, or a 1 if we hit the target
if (subtotal > target) return 0;
if (subtotal === target) return 1;
// we're below the target, so choose next coin
for (var c = coin; c < coins.length; c++) {
// call add_coin() again and add the result to sub_combos
sub_combos += add_coin(c,subtotal);
}
// return the accumulated sub_combos once all coins have been tried
return sub_combos;
}
sub_combos- holds the running total of sub-combinations in the current instance ofadd_coin()subtotal- keeps track of the value of our current set of coins.
It's important to understand that each instance of add_coin() has its very own sub_combos, which doesn't interact with any other level until it is returned.
Basically what is happening is that each time add_coin() is called, a new sub_combos is set up and the value of the new coin is added to subtotal. Unless subtotal matches or exceeds the target, it will call add_coin() again. When the target is reached, it will return a value to the level above it, increment that level's sub_combos and continue the process with the next coin, until all levels run out of smaller coins and return cascading to the top.
You can see here that we're only ever adding 1 to sub_total. That means that whatever the output is (SPOILER: it's 73682), add_coin() must have run at least that many times!
Another interesting thing to note is that since the function only adds a single coin, the number of coins you currently have is the same as the number of levels deep into the recursion you are. Since the maximum number of coins is 200 (200x1p), the program will go 200 levels deep!
The Origin of Complexity
An algorithm is like a piece of music. In the same way that great music has not a note too many, beautiful algorithms are short and stylish. Recursion is a way to cheat, almost, a way to do more than you should be able to. The fact that meaningful recursion even exists can boggle the mind.
Boggling though it is, recursion is a fundamental mechanism of life itself. The origin of complexity. To go from sprout to spruce, you don't need DNA for every branch. You just need the right equation.
So when I'm building a recursive algorithm, I can't help but feel like I'm doing something really sneaky, like I'm stealing a tool from nature's toolshed, which, if my logic is sound, makes me Prometheus, and nature? Well, I'm sure nature has something in store for me.