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:
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
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:
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
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.
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.
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).
None
, or the string 'cheese'
(no pun intended)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:
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.
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
(11, 'cheese')
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