Recursive functions have gotten a bad rap for being slower and using more stack memory than iterative functions, to the point where some developers think they don’t need to master the technique of recursion because it isn’t practical. This is a misconception, and it’s not the only common misconception about recursion.
Recursion as an algorithmic technique is immensely practical. At the heart of iteration is a recursive algorithm: the “ForLoop”.
ForLoop(n) =
0. Let i be 1.
1. If i > n, done.
2. Execute some code.
3. Increment i.
4. Go to step 1.
This is recursive! Within ForLoop, we invoke part of ForLoop.
ForLoop, and many other recursive algorithms, can be implemented iteratively. Some developers will trivialize the task by saying, “Just use a stack!”. But is it really that simple? I would contend it’s not, and it deserves a deeper look.
DFS is the classic recursive algorithm that can easily be implemented iteratively with a stack. But confusingly, the textbook iterative implementation of DFS is not an example of the “Just use a stack!” technique.
DFS (depth first search) is a recursive algorithm:
DFS(v) =
1. Execute some code on v.
2. Mark v as visited.
3. For each neighbor of v, DFS(neighbor) unless neighbor is visited.
Here’s the code for “textbook iterative DFS”:
while stack:
node = stack.pop()
if not visited[node]:
# Execute some code on node
visit()
visited[node] = true
for neighbor in node.neighbors():
if not visited[neighbor]:
stack.push(neighbor)
Notice that we push all unvisited neighbors of a node onto the stack. In a graph where
each vertex has many neighbors - ie a complete graph - stack memory usage will grow quadratically
to the number of vertices in the graph: first n-1 nodes would get pushed onto the stack,
then n-2 (since the previous node was visited), and so on.
We can do better if we avoid storing all neighbors on the stack upfront, and instead store them when needed. The “Just use a stack!” general strategy of turning a recursive algorithm into an iterative algorithm achieves this for DFS, reducing the memory usage from quadratic to linear. We’ll dive into that next.
The core idea behind it is to observe the call stack of recursive function DFS, and then emulate it using iterative constructs.
The call stack of a DFS at any time is the search path up until and including the node we’re currently visited. For example, if we were doing a DFS traversal of Best Buy’s product tree, we may witness a call stack like this at some point in time:
Home -> Electronics -> TV -> LG -> LG500
Say LG500 has no unvisited neighbors. At this point the computer should pop the LG500 stack frame.
Home -> Electronics -> TV -> LG
Then the computer should push on the next unvisited neighbor in the LG stack frame. Let’s call it LG600.
Home -> Electronics -> TV -> LG -> LG600
And maybe LG600 is the last product in the LG product line, which is the last TV brand.
Home -> Electronics -> TV -> LG
Home -> Electronics -> TV
Some iterative code comes to fruition: when we examine the head of the stack, we increment the neighbor index stored in the node, and if it represents a valid neighbor, then we create a stack frame for the neighbor and push it onto the stack.
And on top of this logic, is a while loop that says, while stack is not empty, examine the head of the stack and take some action. When do we pop a stack frame off the stack? When it has no more unvisited neighbors to push onto the stack.
Here’s the corresponding python for the above iterative implementation of the recursive DFS algorithm:
# Stack Nodes
NODE = 0
LAST_NBR_INDEX = 1
# Graph Nodes
LABEL = 0
NBRS = 1
def dfs(n):
stack = [[n, 0]]
visited = set([])
while stack:
# DEBUG
print [stackNode[NODE][LABEL] for stackNode in stack]
headOfStack = stack[-1]
node, nbrIndex = headOfStack
label, nbrs = node
if nbrIndex == -1:
# Execute arbitrary visit code here.
visited.add(node)
i = 0
nextNode = node
while nbrIndex + i < len(nbrs) and nextNode in visited:
nextNode = nbrs[nbrIndex + i]
i += 1
if nextNode not in visited:
# Save our execution state so we can resume when we are popped off next.
headOfStack[LAST_NBR_INDEX] = nbrIndex + i - 1
# Cause loop to examine nextNode next.
stack.append([nextNode, 0])
else:
stack.pop()
When run on this test case:
a = ('LG500', ())
b = ('LG600', ())
c = ('LG', (a, b))
d = ('TV', (c,))
e = ('Home', (d,))
dfs(e)
It outputs:
['Home']
['Home', 'TV']
['Home', 'TV', 'LG']
['Home', 'TV', 'LG', 'LG500']
['Home', 'TV', 'LG']
['Home', 'TV', 'LG', 'LG600']
['Home', 'TV', 'LG']
['Home', 'TV']
['Home']
You’ll notice this DFS code is more complex than the textbook DFS implementation. But, we avoid storing all neighbors of a node on the stack. Instead, we do it lazily by pausing the neighbor iteration, performing the recursive call on a neighbor, and then resuming the neighbor iteration.
For a more detailed analysis of space complexity, see http://wcipeg.com/wiki/Depth-first_search#Space
There are other cases where recursion is useful without necessarily involving recursive functions.
The stack in the DFS implementation above is all you need to resume the algorithm
from that state. This can be useful for being able to resume long computations
after an error.
If an algorithm makes more than one recursive call in an iteration, it might be possible to distribute the work of those recursive calls to multiple processors or machines for parallel execution. So rather than having, say, two recursive function calls in your function body, you can send two messages to a worker pool instead and wait for their responses.
Recursion isn’t just about writing a function that calls itself. It’s an important technique that deserves to be understood more rigorously.