A King is a Son of a King: Recursion
Image by Torley on Flickr
Recursion is often described as something defined in terms of itself. It's used in math, programming, art, and other places.
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.
SNAP! Lecture by Professor Dan Garcia
(find recursion around minute 21)
UC Berkeley, The Beauty and Joy of Computing-Recursion
Tower of Hanoi
The Art and Ideas Behind M. C. Escher’s Drawings
The Nature of Code
Also In The July 2016 Issue
Tinkercad makes it easy to create and print 3D objects from your designs and designs others create.
Bakuro puzzles are a fun way to learn about binary numbers and how to calculate their values.
Figuring out how to find prime numbers is a matter of the right strategy plus code plus trying different ideas.
There are many ways to learn technology while playing. Here are technologies and resources you might want to find online this summer.
A super portable version of Makey Makey, there's lots of experiments you can do with the new Makey Makey Go!
A computational fairytale updated for the computer age, a grasshopper learns algorithms and planning ahead.
A book about the daily life of many different programmers who do neat things with code.
The US Congressional App Challenge is an annual contest to encourage US high school students to try programming by creating an app.
The Alda programming language lets you write and play music on your computer by typing simple commands.
Younger kids can have lots of fun playing games this summer while learning basic programming concepts.
Minecraft is a fun game to explore with a vast set of worlds, animals, and adventures. Here are ideas to continue the adventure, online and offline.
Battery history is a critical part of the history of technology. Without stored electricity, there would be no electronics.
Links from the bottom of all the June 2016 articles, collected in one place for you to print, share, or bookmark.
Interesting stories about computer science, software programming, and technology for June 2016.