Page 1 of 3
Recursion is often said to separate real programmers from the pack. What is it that makes it so powerful? What is it that makes it so difficult? What is the "shape" of recursion?
Let's get the standard joke out of the way right at the start.
Definition of recursion:
Recursion - see Recursion.
There are some who just take to this idea like a duck to water and there are others, the majority, who always feel a little unsure that they have really understood how it all works. To cut to the point, it is a really interesting idea and if you don’t know about it already then you can look forward to some fun.
Ways of repeating things
Before we move on to recursion we need to look at the most basic ways of repeating something - if only to make sure we are using the same vocabulary.
When you first learn to program one of the key ideas is writing a set of instructions that repeats. For example, to print “Hello” repeatedly then I’d use a loop:
You can think of the Loop as an instruction to go back to the Do and repeat all of the instructions between the two all over again. In this case you just go round and round the loop forever printing “Hello” each time.
This is an infinite loop, but most loops in sets of instructions are finite loops which repeat a number of times.
There are two broad types of finite loop, enumeration and conditional.
The difference is that an enumeration loop repeats a given number of times, i.e. print hello five times is an enumeration loop, as is the familiar For loop found in most programming languages.
A conditional loop keeps on repeating until a final end result is achieved, i.e. "stir the coffee until the sugar has dissolved" is a conditional loop, as are the familiar While or Until loops found in most programming languages.
A loop is called a loop because it … loops
To state the most obvious fact about a loop - a loop is called a loop, because it loops around in the text of a program. If you take your finger and follow the sequence of instructions that occur when you have a loop - i.e. the flow of control - then you discover that you are making circular movements as you go back and repeat instructions.
There is a very deep sense in which every programmer thinks of a loop as a circular shape.
So far so good but what has all of this got to do with something far less well known – recursion?
Well recursion is just another way of repeating things. It’s simple at first but stay alert because it has a habit of becoming complicated just when you think you are getting used to it.
Imagine that instead of simply using a command to print a message we write a function (or a procedure), i.e. a self-contained module that does the job and perhaps more. Let’s call it Greetings
lines of instructions
Whenever you use its name the set of instructions is obeyed. So:
results in all of the instructions in the function being obeyed. In this case all that happens is that "Hello" is printed.
This is really all we need to move on to recursion. Consider the following small change:
lines of instructions
What does this do?
If you start it off with a Call Greetings in some other part of the program you start the list of instructions it contains executing. Everything is normal until you get to the Call Greetings instruction, which starts the whole thing going again. We have an infinite loop built using the trick of having a function call itself!
This is the essence of recursion but in this simple form it just looks like an alternative way of creating a loop.
However creating a loop using self reference quickly becomes so much more and its all to do with the way self reference automatically stores the state of things each time you call the function.