I recently read an article about NASA code quality rules and one of these rules is to avoid recursive functions (that are complex to understand and to debug).
I am working on a graph like this:
O
|
O
/ \
O O
/ \ / \
O O O O
It consists of nodes, and every node can have a number of next nodes.
When I need to write a function to go through this kind of graph, I usually create a recursive one, implementing a depth-first traversal:
For every node I visit, I compute whatever I need regarding the current node and then I list the next nodes and call my function on those.
I was wondering if there is a way to perform this kind of traversal without recursion.
I tried to do it with X nested for loops (where X represents the max depth of the traversal), but it did not seem that clean.
I thought about while loops, but I am usually avoiding it.
I have an input list of node names related to next node names:
node_items = [
{
"node_name": "A",
"next_node_names": [
"B"
],
},
{
"node_name": "B",
"next_node_names": [
"C", "D",
],
},
{
"node_name": "C",
"next_node_names": [
"F"
],
},
...
]
Now, my usual recursive function allows me to only have 1 loop in the function, which makes it easy to understand:
def my_recursive_func(current_node_name: str, node_list) -> str:
# select the node in the list
node = next(node for node in node_list if node["name"] == current_node_name)
# computing something related to node
output = ...
# Running on next node
for next_node_name on node["next_node_names"]:
output += my_recursive_function(current_node_name=next_node_name, node_list=node_list)
return output
How can I code this in a clean way without recursion?
This depends much on what the type of processing you actually need to do. For instance, if the order of traversal is not relevant for the calculation, you could use a breadth-first approach, using a FIFO queue. If depth-first traversal is essential, you could implement an explicit stack. Or if the calculation is post-order, then you could first identify the leaves of the tree, do the calculation for those, and then remove these from the tree. Then repeat for the new set of leaves, etc.
Concerning the code you have given, you should avoid this:
node = next(node for node in node_list if node["name"] == current_node_name)
This iteration over the list of nodes worsens the time complexity of the algorithm. Instead, first key your data structure by node name, turning it into an adjacency list data structure.
Your example -- made concrete with a "calculation" -- then becomes:
def create_adj_list(items):
adj = {}
for obj in items:
adj[obj["node_name"]] = obj["next_node_names"]
for child in obj["next_node_names"]:
if child not in adj:
adj[child] = []
return adj
def my_recursive_func(current_node_name: str, adj) -> str:
# computing something related to node
output = current_node_name + "("
# Running on next node
for next_node_name in adj[current_node_name]:
output += my_recursive_func(next_node_name, adj)
return output + ")"
adj = create_adj_list(node_items)
res = my_recursive_func("A", adj)
If you would mimic this with an explicit stack, you could get something like this:
def my_iterative_func(start_node: str, adj) -> str:
stack = [[start_node, iter(adj[start_node]), start_node + "("]]
while True:
node, child_iter, result = stack[-1]
child = next(child_iter, None)
if child is not None:
stack.append([child, iter(adj[child]), child + "("])
else:
stack.pop()
result += ")"
if not stack:
return result
stack[-1][2] += result