Sitemap
Towards AI

The leading AI community and content platform focused on making AI accessible to all. Check out our new course platform: https://academy.towardsai.net/courses/beginner-to-advanced-llm-dev

Follow publication

Visualizing Recursion Trees

18 min readMar 23, 2025

--

Zoom image will be displayed
Recursion Execution path, Gif by Author

How to reproduce

Motivation

Existing options

Requirements

Results

The plan

The journey

Zoom image will be displayed
Photo by Nicolas Hoizey on Unsplash

The Function

def permute(nums):
def backtrack(first=0):
if first == len(nums) - 1:
result.append(nums[:])
return
for i in range(first, len(nums)):
nums[first], nums[i] = nums[i], nums[first] # Swap numbers
backtrack(first + 1)
nums[first], nums[i] = nums[i], nums[first] # Swap back

result = []
backtrack()
return result


print(permute([1, 2, 3]))
# Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

Indentation to track execution

def permute(nums):

depth = 0

def backtrack(first=0):

nonlocal depth # Use nonlocal to modify the 'depth' variable from the enclosing scope

print(" " * depth + f"backtrack(first={first}, nums={nums})")

if first == len(nums) - 1:
result.append(nums[:])
return

for i in range(first, len(nums)):
print(" " * depth + f"swapping {nums[i]} and {nums[first]}")
nums[first], nums[i] = nums[i], nums[first]

depth += 1
backtrack(first + 1)
depth -= 1

print(" " * depth + f"swapping back {nums[first]} and {nums[i]}")
nums[first], nums[i] = nums[i], nums[first]

result = []
backtrack()
return result


print(permute([1, 2, 3]))

Truncated Output

backtrack(first=0, nums=[1, 2, 3])
swapping 1 and 1
backtrack(first=1, nums=[1, 2, 3])
swapping 2 and 2
backtrack(first=2, nums=[1, 2, 3])
swapping back 2 and 2
swapping 3 and 2
backtrack(first=2, nums=[1, 3, 2])
swapping back 3 and 2
swapping back 1 and 1
---------------------------TRUNCATED--------------------------------

Limitations

Graphviz

from graphviz import Digraph


def permute(nums):
graph = Digraph(format="png")
node_id = 0 # Unique ID for each node

def backtrack(first=0, depth=0, parent=None):
nonlocal node_id
node_label = f"{first}: {nums}" # Label for current node
current_id = str(node_id)
graph.node(current_id, label=node_label)
node_id += 1

if parent is not None:
graph.edge(parent, current_id) # Draw edge from parent to current node

if first == len(nums) - 1:
return

for i in range(first, len(nums)):
nums[first], nums[i] = nums[i], nums[first] # Swap numbers
backtrack(first + 1, depth + 1, current_id)
nums[first], nums[i] = nums[i], nums[first] # Swap back

backtrack()

# graph.render("recursion_tree", view=True) # Save and open the tree
return graph


# Run the function
graph = permute([1, 2, 3])
print(graph)
graph
Zoom image will be displayed
Graphviz tree, Image from Author
digraph {
0 [label="0: [1, 2, 3]"]
1 [label="1: [1, 2, 3]"]
0 -> 1
2 [label="2: [1, 2, 3]"]
1 -> 2
3 [label="2: [1, 3, 2]"]
1 -> 3
4 [label="1: [2, 1, 3]"]
0 -> 4
5 [label="2: [2, 1, 3]"]
4 -> 5
6 [label="2: [2, 3, 1]"]
4 -> 6
7 [label="1: [3, 2, 1]"]
0 -> 7
8 [label="2: [3, 2, 1]"]
7 -> 8
9 [label="2: [3, 1, 2]"]
7 -> 9
}

Increasing coupling of supporting functionality

Zoom image will be displayed
Photo by T R on Unsplash

Adding interactivity with D3

with open("graph_data.json", "w") as f:
json.dump(graph_data, f)

f"""
<!DOCTYPE html>
<html>
<!----------------------TRUNCATED SECTION --------------------->
</html>
"""

with open("visualization.html", "w") as f:
f.write(html_code)

Getting around CORS error

Zoom image will be displayed
NetworkX diagram, Image from Author

Plotly with ipywidget

Zoom image will be displayed
Plotly scatterplot, Image from Author
Zoom image will be displayed
Photo by Matt Bluejay on Unsplash

ax.plot (not refreshing)

import matplotlib.pyplot as plt
import ipywidgets as widgets
from graphviz import Digraph
from io import BytesIO
from IPython.display import display, clear_output


# Generate the recursion tree and track nodes
def permute(nums):
graph = Digraph(format="png")
node_id = 0 # Unique ID for each node
nodes_data = [] # Store nodes and their depth

def backtrack(first=0, depth=0, parent=None):
nonlocal node_id
node_label = f"{first}: {nums}" # Label for the current node
current_id = str(node_id)

# Add the current node to the Graphviz tree
graph.node(current_id, label=node_label)

if parent is not None:
graph.edge(parent, current_id) # Add edge from parent to current node

# Store the node and its depth for later use in the visualization
nodes_data.append((current_id, depth))
node_id += 1

if first == len(nums) - 1:
return

# Recursive backtracking to generate permutations
for i in range(first, len(nums)):
nums[first], nums[i] = nums[i], nums[first] # Swap numbers
backtrack(first + 1, depth + 1, current_id) # Recurse
nums[first], nums[i] = nums[i], nums[first] # Swap back

# Generate the recursion tree
backtrack()

return nodes_data, graph


# Draw the tree and highlight nodes iteratively using a slider
def draw_graph(nodes_data, graph, num_iterations):
fig, ax = plt.subplots(figsize=(10, 8))

# Function to render the graph to a BytesIO object (in memory)
def render_graph():
# Render graph to a byte stream in memory using pipe()
output = graph.pipe(format="png") # Render to memory (PNG format)
img_bytes = BytesIO(output)
img = plt.imread(img_bytes) # Read the PNG from the byte stream

return img

# Display the initial graph
img = render_graph()
ax.axis("off")
plt.imshow(img)

# Create the slider widget to control iteration progress
slider = widgets.IntSlider(value=0, min=0, max=num_iterations - 1, step=1, description="Iteration:")
display(slider)

# Function to update the graph and highlight nodes based on the slider value
def update_graph(change):
# Get the nodes to highlight based on the slider value
clear_output(wait=True)
display(slider)

iteration = slider.value
highlighted_nodes = nodes_data[: iteration + 1] # All nodes up to this iteration

# Reset node colors before modifying
for node_id, _ in nodes_data:
graph.node(node_id, color="black", style="filled", fillcolor="white")

for i, (node_id, _) in enumerate(highlighted_nodes):
graph.node(node_id, style="filled", fillcolor="lightblue")

# Render the updated graph to the byte stream and get the image
img = render_graph()

ax.clear()
ax.axis("off")
ax.imshow(img)
fig.canvas.draw()

# Connect the slider to the update function
slider.observe(update_graph, names="value")


# Run the program
nums = [1, 2, 3]
nodes_data, graph = permute(nums) # Generate the recursion tree and the nodes data
num_iterations = len(nodes_data) # Number of iterations equals the number of nodes
draw_graph(nodes_data, graph, num_iterations) # Draw the graph with interactive slider

The bug

Zoom image will be displayed
Photo by Markus Winkler on Unsplash

A simpler example

plt.show

        img = render_graph()

ax.clear()
ax.axis("off")
ax.imshow(img)
fig.canvas.draw()
        img = render_graph()

ax.axis("off")
plt.imshow(img)

ax.plot (working)

        img = render_graph()

ax.clear()
ax.axis("off")
ax.imshow(img)
# fig.canvas.draw()
display(fig)

Comparing ax.imshow vs plt.imshow

Pushing for Improvements

Zoom image will be displayed
Photo by Spenser Sembrat on Unsplash

Decorators

Class-based vs Function-based

def retry(retries=3, delay=1):
# This is the first layer of nesting: the function that takes the decorator arguments
def decorator(func):
# This is the second layer of nesting: the actual decorator function
def wrapper(*args, **kwargs):
##### TRUNCATED #####
return wrapper
return decorator

# Usage
@retry(retries=5, delay=2)
def unreliable_function():
##### TRUNCATED #####
class RetryDecorator:
def __init__(self, retries=3, delay=1):
self.retries = retries
self.delay = delay

def __call__(self, func):
def wrapper(*args, **kwargs):
##### TRUNCATED #####
return wrapper

# Usage
@RetryDecorator(retries=5, delay=2)
def unreliable_function():
##### TRUNCATED #####

Side tour of Function-based decorators

class CountCalls:
def __init__(self, func):
self.func = func
self.count = 0
def __call__(self, *args, **kwargs):
self.count += 1
print(f"# of calls: {self.count}")
return self.func(*args, **kwargs)
@CountCalls
def foo(x):
return x + 2

@CountCalls
def foo2(x):
return x + 2

foo(2)
foo(2)

foo2(2)
foo2(2)
Zoom image will be displayed
Photo by Nathan Dumlao on Unsplash

Back to Class-based decorator

class Visualizer:
def __init__(self, func):
self.func = func
self.graph = Digraph(format="png")
self.node_id = 0
self.parent = None
self.depth = -1
self.nodes_data = []

def __call__(self, *args, **kwargs):
node_label = f"{args=}"
current_id = str(self.node_id)
self.node_id += 1
self.graph.node(current_id, label=node_label)

if self.parent is not None:
self.graph.edge(self.parent, current_id)

self.nodes_data.append((current_id, self.depth + 1))

previous_parent = self.parent
self.parent = current_id
self.depth += 1

self.func(*args, **kwargs)

self.parent = previous_parent
self.depth -= 1

return self.nodes_data, self.graph

Parent-Child handling

previous_parent = self.parent
self.parent = current_id

self.func(*args, **kwargs)

self.parent = previous_parent

General Applicability

# @Visualizer
# def f(n):
# if n == 1:
# return 1
# return f(n - 1) * n

Debugging Side Quest

self.parent = current_id # add bug
self.nodes_data.append((current_id, self.depth + 1))

previous_parent = self.parent
self.parent = current_id
digraph {
0 [label="args=([1, 2, 3],)"]
1 [label="args=([1, 2, 3], 1)"]
0 -> 1
2 [label="args=([1, 2, 3], 2)"]
1 -> 2
3 [label="args=([1, 3, 2], 2)"]
2 -> 3
4 [label="args=([2, 1, 3], 1)"]
1 -> 4
5 [label="args=([2, 1, 3], 2)"]
4 -> 5
6 [label="args=([2, 3, 1], 2)"]
5 -> 6
7 [label="args=([3, 2, 1], 1)"]
4 -> 7
8 [label="args=([3, 2, 1], 2)"]
7 -> 8
9 [label="args=([3, 1, 2], 2)"]
8 -> 9
}
Zoom image will be displayed
Buggy Graphviz tree, Image by Author

Possible Extensions

Other tools

Zoom image will be displayed
Photo by ANIRUDH on Unsplash

Lessons

Unexpected discoveries

UX

Prompt efficiency

Zoom image will be displayed
Fire Water YinYang Generated by Image Creator

Balance

Abstraction level

One-factor-at-a-time

Conclusion

References

--

--

Towards AI
Towards AI

Published in Towards AI

The leading AI community and content platform focused on making AI accessible to all. Check out our new course platform: https://academy.towardsai.net/courses/beginner-to-advanced-llm-dev

Han Qi
Han Qi

Written by Han Qi

Shares ideas that I can’t find online. You can support my writing by joining Medium through https://hanqi01.medium.com/membership (affiliate link)

Responses (3)