Recursion

What is recursion?

Recursion is describing a term, or, like in computer programming, a procedure in terms of itself. Ironically the definition of recursion in the Oxford English Dictionary is recursive itself:

Recursion: the repeated application of a recursive procedure or definition.

This seems to cause more problems than it solves. After all, when you would look up “recursive”, and it points to “recursive”, you'll end up in an infinite loop. So for use in algorithms we must add something to the definition:

Recursive algorithm: algorithm which includes a simpler version of itself

This already makes more sense. With each iteration you go through a simpler version of the algorithm, until you reach the point where the problem becomes trivial.

Towers of Hanoi

In programming courses Towers of Hanoi is often used as a typical problem for a recursive solution. Here's the problem, originally defined by the mathematician Édouard Lucas: you have 3 pegs with on the first one a stack of discs of different diameters. A disc always sits on a larger one, so the stack is sorted from largest to smallest. The task is to move the stack to the third peg via the second peg, one disc at a time, and never placing a larger disc on top of a smaller one. According to a legend of unknown origin Brahmin priests have been moving discs from a 64 disc stack at a rate of one move per second. We'll see that for an N disc stack 2^N-1 moves are needed, so for a 64 disc stack that's 2⁶⁴-1 or 585 billion years, so you may want to sit down for this. We'll solve the puzzle for 4 discs by hand. For larger stacks the same algorithm can be used.

How is recursion going to help us, or in other words: how can I describe the problem in a simpler form of itself, being "Move 4 discs from A to C? A simpler form could be to move 3 discs instead of 4. Then the algorithm becomes:

1. Move a stack of 3 discs from peg A to peg B
2. Move the remaining disc from peg A to peg C
3. Move the stack of 3 discs from peg B to peg C

1. Move a stack of 3 discs from peg A to peg B
   1. Move a stack of 2 discs from peg A to peg C
   2. Move the next disc from peg A to peg B
   3. Move the stack of 2 discs from peg C to peg B
2. Move the remaining disc of peg A to peg C
3. Move the stack of 3 discs from peg B to peg C
   1. Move a stack of 2 discs from peg B to peg A
   2. Move the next disc from peg B to peg C
   3. Move the stack of 2 discs from peg A to peg C

So in general for "move N discs from source to destination" we have

1. Move N-1 discs from source to auxilliary
2. Move 1 disc from source to destination
3. Move N-1 discs from auxilliary to destination

The program in pseudocode

Procedure Main():
    Hanoi(64, A, C, B);
end
          
Procedure Hanoi(N, source, destination, auxilliary)
    if N > 1 then
        Hanoi(N-1, source, auxilliary, destination);
        Move(source, destination);
        Hanoi(N-1, auxilliary, destination, source);
    else
        Move(source, destination);
end
          
Procedure Move(source, destination)
    Print(source + " to " + destination);
end

When recursion is bad

Recursion is a powerful technique, but isn't always appropriate. The Fibonacci sequence is often mentioned as an example of recursion, but it's awful to program it recursively. Let's look at the Fibonacci number sequence $F(n)$, which is defined as follows: $$ F(n) = \begin{cases} 1, & \mbox{if } n \le 2 \\ F(n-1) + F(n-2), & \mbox{if } n > 2 \end{cases} $$ That's indeed a recursive definition. For instance $F(42) = F(41) + F(40)$. So why would it be bad to program this recursively? If you would calculate $F(41)$ in the example, you'd start by calculating $F(41 - 1)$, or $F(40)$, but you would calculate $F(40)$ again as the second term of the original sum. You'll do much extraneous work. And by much I really mean a lot. Let's see how it unfolds: $$ \begin{array} {rcl} F(42) & = & F(41) + F(40) \\ & = & (F(40) + F(39)) + (F(39) + F(38)) \\ & = & ((F(39) + F(38)) + (F(38) + F(37)) + ((F(38) + F(37)) + (F(37) + F(36)) \end{array} $$ The next step will have 16 terms, the one after that 32, and so on. Not only that, but we'd be calculating terms again and again. Here we already have three times $F(38)$ and $F(37)$, so their expansion will become three times the same sum. It appears that the number of sums needed to find $F(n)$ is $F(n) - 1$, and the following table shows how quickly this escalates:

The last calculation has nearly 33 billion additions and takes 2.5 minutes on my computer (Jan 2026). $F(100)$ = 354 224 848 179 261 915 075 which would take tens of thousands of years to calculate.

So recursion is not always a good idea. Much better is to use common iteration, starting from $F(3) = F(2) + F(1)$, and storing that result, together with $F(2)$, because we'll need that for the next step: $F(4) = F(3) + F(2)$, values you already have, so that's just one addition. Again store $F(3)$ and $F(2)$ for the next step. To calculate $F(50)$ we only need 50 additions instead of 33 billion.