If you have had the pleasure of reading Stephen Hawking’s A Brief History of Time (or A Briefer History of Time), you may recall the following passage:
A well-known scientist (some say it was Bertrand Russell) once gave a public lecture on astronomy. He described how the earth orbits around the sun and how the sun, in turn, orbits around the center of a vast collection of stars called our galaxy. At the end of the lecture, a little old lady at the back of the room got up and said: “What you have told us is rubbish. The world is really a flat plate supported on the back of a giant tortoise.” The scientist gave a superior smile before replying, “What is the tortoise standing on?” “You’re very clever, young man, very clever,” said the old lady. “But it’s turtles all the way down!” — Hawking
The origins of the phrase “turtles all the way down” is not completely agreed upon, however it leads most people to the same question: What is the first turtle standing on? Similarly, the slightly more plausible statement “A king is a son of a king” might lead us to wonder who was the first king.
Conundrums such as these provide us with examples of recursion in language. Recursion is often described as something defined in terms of itself. In fact, if we look up recursion in the Urban dictionary, we find the humorous, but accurate, entry “Recursion: see recursion”.
In examples such as these, recursion might come across as a mind bender with little practical application. However in both math and computer science, we can use recursion as a powerful problem-solving technique. Defining recursion by instructing us to look up recursion seems to be of little use at first, however this definition actually works perfectly. Similarly, when we first explore recursive functions in programming, they might appear somewhat undefined and empty. Yet when we walk through them, we find that they too work perfectly. This perhaps is one of the defining marks of recursion.
Take for example the famous Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, …….
Many people familiar with this sequence would describe it by saying that the first and second terms are both one and that each subsequent term is the sum of the two previous terms. In other words, to calculate the nth term, we add up the (n-1)th term and the (n-2)th term. That all sounds simple enough, but what if we don’t know these two terms yet? We just keep moving down the line until we get to the first two terms and begin adding. It’s not so different from turtles all the way down, except fortunately we have a clearly defined beginning, one and one. And if we want to know the nth term of the sequence we can write a recursive program to calculate it.
Take a look at the Python code below in which we define a function called fib that returns the nth term of the Fibonacci sequence:
def fib(n):
if n == 1 or n == 2:
return 1
else:
return fib(n-1)+fib(n-2)
If we type in fib(1) or fib(2), the program will return the value 1. Now consider what will happen if we want to know the 5th term of the Fibonacci sequence. We begin by typing fib(5). The program will jump down to the final line to return fib(4) + fib(3). However we never told the computer the value of the 4th or 3rd terms of the sequence, so it might feel as though we are just spinning our wheels.
Fortunately that is not the case. The fib(n) function calls itself, this time with the values of n = 4 and n = 3. This is what makes the function recursive: it calls itself from within. For n = 4 we come up with fib(3) + fib(2), and for n = 3 we call the function again to get fib(2) + fib(1). All in all we have (fib(3) + fib(2)) + (fib(2) + fib(1)). In each case the function calls itself again. It still does not know fib(3), but it does know that fib(1) and fib(2) both return the value 1, leaving us with fib(3) + 1 + 1 + 1. As for fib(3), the function calls itself yet again with a value of n = 3, and comes up with fib(2) + fib(1). All in all we get 1 + 1 + 1 + 1 + 1, telling us that the fifth term of the Fibonacci sequence is 5.
As it turns out, we find recursive patterns all over math and computer science. Take for example Pascal’s triangle, factorials, or the Tower of Hanoi. All three refer back to themselves to generate subsequent terms. To complete the 4th row of Pascal’s triangle, we refer back to the third row and so on up. To calculate the factorial of 6, we can take the factorial of 5 and multiply it by 6. In order to know the factorial of 5, we look to the factorial of 4 and so on. And for the Tower of Hanoi, we can complete the challenge of moving all the disks from one peg to another by moving all but the bottom disk to another peg, then moving the bottom disk, recursively. As such, each of these ideas can be programmed with just a few lines of code.
If Fibonacci numbers, Pascal’s triangle, factorials, and the Tower of Hanoi can all be defined recursively, we might imagine that there could be recursion in nature and art as well. In fact, fractals such as Sierpinski’s triangle triangle, fractal trees, and the Mandelbrot Set are just three of many beautiful examples of recursion.
It is not often that we find an idea that spans language play, math, computer science, and art. However recursion does just that. Now that you have a bit of practice under your belt, you are sure to find recursive ideas in all sorts of places.
Learn More
SNAP! Lecture by Professor Dan Garcia
(find recursion around minute 21)
https://www.youtube.com/watch?v=ysq-wvq7eSY
UC Berkeley, The Beauty and Joy of Computing-Recursion
https://www.youtube.com/watch?v=JKn3nsfzBdA
Tower of Hanoi
http://www.python-course.eu/towers_of_hanoi.php
Recursivity
http://gregtatum.com/poems/recursive/5/
Unbounded Recursion
http://wiki.secretgeek.net/unbounded-recursion
The Art and Ideas Behind M. C. Escher’s Drawings
http://www.pxleyes.com/blog/2010/06/recursion-the-art-and-ideas-behind-m-c-eschers-drawings/
