Motivating and Visualizing Recursion in Python

Recursive factorial function considered harmful

Gustavo Duarte (@food4hackers) wrote about Recursion: Dream within a Dream, arguing for the use of well-motivated examples to teach recursion, "the single most powerful idea in algorithms".

He crafts a compelling critique of a common example used to demonstrate recursion (an example that I, myself, have often used in the past): the factorial function,

$$n! = \prod_{k=1}^{n} k$$

A recursive version of the factorial function can be defined in Python as follows:

In [1]:
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Gustavo notes:

Our factorial algorithm boils down to pushing integers N, N-1, … 1 onto a stack, then multiplying them in reverse order. The fact we’re using the program’s call stack to do this is an implementation detail: we could allocate a stack on the heap and use that instead.

...

Once you see the call stack as a data structure, something else becomes clear: piling up all those integers to multiply them afterwards is one dumb-ass idea. That is the real lameness of this implementation: it’s using a screwdriver to hammer a nail. It’s far more sensible to use an iterative process to calculate factorials.

An iterative version of the function can be defined in Python as follows

In [6]:
def i_factorial(n):
    product = 1
    for k in range(1, n + 1):
        product *= k
    return product

We can verify the functional equivalence of these two versions:

In [7]:
for k in range(10):
    print '{}! = {:6d}, {:6d}'.format(k, factorial(k), i_factorial(k))
0! =      1,      1
1! =      1,      1
2! =      2,      2
3! =      6,      6
4! =     24,     24
5! =    120,    120
6! =    720,    720
7! =   5040,   5040
8! =  40320,  40320
9! = 362880, 362880

Recursion: an a-maze-ing way to traverse a tree

Gustavo proposes demonstrating the use - and value - of recursion by selecting a more appropriate problem, where a non-recursive (iterative) approach would be far more cumbersome: exploring a maze, where the maze is represented as a binary tree.

when it comes to algorithms, recursion is the rule, not the exception. It comes up when we search, when we traverse trees and other data structures, when we parse, when we sort: it’s everywhere. You know how pi or e come up in math all the time because they’re in the foundations of the universe? Recursion is like that: it’s in the fabric of computation.

maze

He defines a C struct, mazeNode, with 4 members to represent a node in the binary tree representation of this maze:

typedef struct mazeNode {
        int hasCheese;
        int tag;
        struct mazeNode *left;
        struct mazeNode *right;
} maze_t;

He also defines a recursive C function, explore() to recursively traverse the maze (binary tree), stopping when it finds a node where hasCheese == 1, and visualizes the call stack of the execution of the function when it finds the cheese.

mazeCallStack.png

Recursively traversing a binary tree in Python

maze I could define a Python class to represent a mazeNode, but will choose a simpler approach using 4-element tuples (4-tuples) to represent each node in a tree: (tag, has_cheese, left, right).

  • tag will again be an int (in the range 0 to 11)
  • has_cheese will either be the Python null object, None, or the string 'cheese' (no pun intended)
  • left will be a 4-tuple or empty tuple representing the left branch
  • right will be a 4-tuple or empty tuple representing the right branch
In [10]:
maze = (0, None,
        (1, None,
         (2, None,
          (3, None, (), ()),
          (4, None, (), ())),
         (5, None,
          (6, None, (), ()),
          ())),
        (7, None,
         (8, None, (), ()),
         (9, None,
          (10, None,
           (11, 'cheese', (), ()),
           ()),
          ())))

I typically insert print statements into a recursive function to illustrate the execution call stack. Here's how I might define the explore() function in Python, using an optional depth parameter to visualize call strack trace information:

In [13]:
def explore(node, depth=0):
    if not node: # empty tuple
        print ' <' * depth, 'Nothing found'
        return False
    print ' >' * depth, 'Checking node', node[0]
    if node[1]: # check for non-empty/non-None 2nd element
        print ' *' * depth, 'Found', node[1], 'at node', node[0]
        return node[:2] # return tag and element
    return explore(node[2], depth + 1) or explore(node[3], depth + 1)

Exploring the maze will print out a series of > characters as the function recursively calls itself, where the number of characters indicates the depth of the recursion. A series of < characters are printed when a recursive calls returns after failing to find anything at a node. A series of * characters will be printed if/when a node with 'cheese' (or anything other than None) is found.

In [14]:
explore(maze)
 Checking node 0
 > Checking node 1
 > > Checking node 2
 > > > Checking node 3
 < < < < Nothing found
 < < < < Nothing found
 > > > Checking node 4
 < < < < Nothing found
 < < < < Nothing found
 > > Checking node 5
 > > > Checking node 6
 < < < < Nothing found
 < < < < Nothing found
 < < < Nothing found
 > Checking node 7
 > > Checking node 8
 < < < Nothing found
 < < < Nothing found
 > > Checking node 9
 > > > Checking node 10
 > > > > Checking node 11
 * * * * Found cheese at node 11
Out[14]:
(11, 'cheese')

mazeCallStack.png Selecting the active elements of the printed trace above when the 'cheese' is found shows a similar sequence - in reverse - as depicted in the call stack image that Gustavo created:

 Checking node 0
 > Checking node 7
 > > Checking node 9
 > > > Checking node 10
 > > > > Checking node 11
 * * * * Found cheese at node 11