Emulating Recursion
Recursion is often used as a clean & elegant way to solve a problem by repeatedly solving its sub-problems. The function and power of recursion is derived from usage of the call stack. Each time you recurse, you’re saving the current state of the function in the call stack (e.g. all variables within function scope, the return pointer to where code was last executed in the function)
Python function calls and the stack (by Phil Conrad, link below)
As shown above, every time a new function is called we need to save (1) a return pointer to our current location and (2) the function’s arguments before jumping to the new function. While working through the function, we also save the state of the function’s variables on the stack!
Understanding this, we can emulate recursion by writing our code iteratively (instead of recursively), and managing our own stack in the same manner the call stack is managed.
Recursion + DFS
Below is a typical example of recursion used to traverse a binary tree. The code also keeps track of all existing paths from root to leaf within the tree.
def dfs(node, path, result):
# Leaf node
if node.left == None and node.right == None:
result.append(path + str(node.val))
return result
# Traverse left
if node.left != None:
dfs(node.left, path + str(node.val) + "->", result)
# Traverse right
if node.right != None:
dfs(node.right, path + str(node.val) + "->", result)
return result
def binaryTreePaths(root):
return dfs(root, "", [])
Stack + DFS
The code below performs the exact same function as that from the previous section. However this code does not use recursion, and instead works iteratively and maintains its own "call stack". This code is also a lot less clean and a lot more verbose. 😭
As shown in line 4, we are now needing to keep track of the node
and path
variables which were previously saved to the call stack as function arguments.
Additionally, we’re needing to save a variable LEAF, LEFT, RIGHT
which acts as a return pointer! When returning from a recursive function, you are able to continue executing exactly where you left off in the parent function. Within a while
loop, we needed to get creative to mimic that same behavior.
def binaryTreePaths(root):
LEAF, LEFT, RIGHT = 0, 1, 2
result = []
stack = [(root, "", LEAF)] # node, path, execution
while len(stack) != 0:
curr, path, exec = stack.pop()
# LEAF Node.
# Add to result, go back to parent node.
if curr.left == None and curr.right == None:
result.append(path + str(curr.val))
continue
# Traverse LEFT (only if not visited yet for this node)
# Add current node back to stack with updated "return pointer". Add left child node to stack.
if exec == LEAF:
if curr.left != None:
stack.append((curr, path, LEFT))
stack.append((curr.left, path + str(curr.val) + "->", LEAF))
continue
# Traverse RIGHT (only if not visited yet for this node)
# Add current node back to stack with updated "return pointer". Add right child node to stack.
if exec == LEAF or exec == LEFT:
if curr.right != None:
stack.append((curr, path, RIGHT))
stack.append((curr.right, path + str(curr.val) + "->", LEAF))
continue
return result
Conclusion
As far as I understand, I don’t believe there is a significant speed / memory advantage to emulating the stack. If that’s what you’re looking for, tail call optimization (maybe?) is the solution for you! More to come as I continue exploring!
References
- https://en.wikipedia.org/wiki/Recursion_(computer_science)
- https://codeforces.com/topic/49210/en11
- https://sites.cs.ucsb.edu/~pconrad/cs8/topics.beta/theStack/04/
- https://softwareengineering.stackexchange.com/questions/303242/is-there-anything-that-can-be-done-with-recursion-that-cant-be-done-with-loops