Previous topic

31. Summary

Next topic

1. Recursion: a simple example

This Page

Recursion

If you look up on the Internet for a definition of recursion, you will often see something like the following:

Recursion
See recursion.

This is wrong, wrong, wrong, wrong .... WRONG!

If you were a computer program, trying to parse the above definition, you would get stuck in an infinite loop. Since you are reading this, it means that either you did not behave like a computer and got stuck in an infinite loop OR that you did not read everything here and, in particular, skipped over the above definition.

Recursion is sometimes described as being difficult to grasp. Do not believe this. If you understand loops, you can understand recursion.

So, what is recursion you ask?...

Recursion is the process of repeating items in a self-similar way. For computer programs, it means repeating instructions - like in a loop. And, like in a loop, we do not want to get stuck forever.

For educators

Some consider recursion to be a very difficult concept to grasp; you should feel free to skip over this part which essentially stands alone.

I’ve chosen to introducer recursion here because, on the one hand all the required prerequisites have been seen and, on the other hand, the recent introduction of the while loop which can often be replaced by recursion, and vice-versa, gives an opportunity to strengthen the understanding of looping. If one waits until later, when the student is thoroughly familiar with while loops which has become second nature to them, the concept of recursion may look to them as something very different and suddenly “very difficult” in comparison.