tracing the recursion tree

← 🏠

Recursive functions become a lot easier to grasp once visualised:

1def func(depth = 0):
2  if depth >= 5:
3      return
4  print(depth)
5  func(depth + 1)
6
7func()

The number on the branch is the number that gets printed, while the func(n) is the actual function call. Let's execute this code by hand, and add some 'syntax highlighting' to the call graph.

Executing a recursive function by hand, and drawing the call-graph with the values of the variables dramatically improves your ability to think and code recursively. By doing so, you're tracking the values of all the variables at each step of the call stack.

It may appear trivial with such a trivial function; however with more complex recursive functions, it becomes a lot more interesting.

Tower of Hanoi

The tower of Hanoi is a classic problem, and has the tendency to create huge classic recursion headaches, as it's very difficult to visualise and intuitively grasp what it's doing.

The aim is to move the disks from one (src) peg to another (dest) peg, while only having smaller disks sitting on top of larger ones.

This recursive algorithm only uses 1 extra tmp peg, as a buffer.

 1def hanoi():
 2    def move(n, src, dest, tmp):
 3        if n > 0:
 4            move(n - 1, src, tmp, dest)
 5            pegs[dest].append(pegs[src].pop())
 6            move(n - 1, tmp, dest, src)
 7    pegs = [[3, 2, 1], [], []]
 8    move(n=3, src=0, dest=2, tmp=1)
 9
10hanoi()

Now before jumping in, let's lay down some further foundations in your thinking toolset, that'll make reasoning and truly understanding it a lot easier, and more intuitive.

Decreasing the `depth`

Instead of incrementing the depth variable, we could initialise it at the depth we are after, and decrement it on each successive call. Let's also rename it to n.

1def func(n):
2  if n < 0:
3      return
4  print(n)
5  func(n - 1)
6
7func(n=5)

Output:

It's now a lot easier to control the recursion depth from the caller. It's also very useful, since the depth or nis the number of disks we'll be working with.

Switching two variables

Now observe what happens in the following code snippet:

1def func(n, a, b):
2  if n < 0:
3      return
4  print(a, b)
5  func(n - 1, b, a)
6
7func(n=5, a=0, b=1)

With each call, we swap the variables a and b. This is pretty similar to what we'll be doing with the Tower of Hanoi problem: with each recursion, we'll swap which disks we refer to as the source, the temp and the dest peg.

Switching three variables

Now observe what happens in the following code snippet:

1def func(n, a, b, c):
2  if n < 0:
3      return
4  print(a, b, c)
5  func(n - 1, c, a, b)
6
7func(n=5, a=0, b=1, c=2)

We are now sliding the values to the right. Again, pretty easy.

Branching

So far, tracing the calls has been easy: there's only one call meaning our recursion "graph" is pretty much a straight line. But what happens when we make two calls instead of one?

 1from string import ascii_lowercase as asc
 2
 3def func(n, a):
 4 if n < 0:
 5     return
 6 func(n - 1, a-1)
 7 print(a)
 8 func(n - 1, a+1)
 9
10func(n=5, a=0)

Well our call-graph now looks like a binary tree, and the values we are printing can, in a way, be thought of as being printed in-order since the print statement is between the two calls.

1 disk

The best way to approach any complex algorithm is to simplify the data on which its working to a bare minimum. So let's begin with a single disk.

With a single disk, things could not be easier: no recursion actually takes place, since we hit the base case. The work we did was equivalent to this:

1def hanoi():
2    def move(n, src, dest, tmp):
3      pegs[dest].append(pegs[src].pop())
4    pegs = [[1], [], []]
5    move(n=1, src=0, dest=2, tmp=1)
6
7hanoi()

Another way of look at things is, imagine we had guards before our recursive calls:

 1def hanoi():
 2    def move(n, src, dest, tmp):
 3        if n > 0:
 4            if n > 1:
 5             move(n - 1, src, tmp, dest)
 6            pegs[dest].append(pegs[src].pop())
 7            if n > 1:
 8             move(n - 1, tmp, dest, src)
 9    pegs = [[1], [], []]
10    move(n=1, src=0, dest=2, tmp=1)
11
12hanoi()

When writing recursive functions, it can be useful to add a guard around the recursive calls rather than hitting the base case. This makes tracing the tree dramatically easier, and greatly reduces the number of calls, and improves the time & space complexity by reducing the call stack size. It does however come at the detriment of legibility.

2 disks

With two disks, things get more interesting. The first call to move invokes move recursively, switching tmp and dest; this performs the preparation work of moving the top disk to the tmp peg. The call then returns, next the actual intended action of moving the large disk from peg 0 to 2 can take place.

Next move gets invoked again, on line 6, thereby switching the src and tmp pegs; this moves the initial smaller disk onto the peg 2, and the puzzle is complete.

Finally we can trace our function with 3 disks.

 1def hanoi():
 2    def move(n, src, dest, tmp):
 3        if n > 0:
 4            move(n - 1, src, tmp, dest)
 5            pegs[dest].append(pegs[src].pop())
 6            move(n - 1, tmp, dest, src)
 7    pegs = [[3, 2, 1], [], []]
 8    move(n=3, src=0, dest=2, tmp=1)
 9
10hanoi()

Obviously the more disks there are, the more complex it becomes tracking precisely what is taking place, and why. But it is absolutely doable; and the reader is encouraged to do so as an exercise.

Recursion is difficult, and in many cases, there are no shortcuts to tracing the calls by hand, and tracking the variables carefully. The more often you do so, the better you'll become at thinking recursively, but it does take time and practice to improve in this particular skill.