These advanced examples demonstrate more sophisticated recursive algorithms including binary string generation, sum permutations, and graph search with the missionaries and cannibals problem.
Binary string generation
Generate all binary strings of a given length:
from visualiser.visualiser import Visualiser as vs
"""
Problem Link: https://stackoverflow.com/questions/33808653/recursion-tree-with-fibonacci-python/60126306#60126306
"""
@vs(node_properties_kwargs={"shape":"record", "color":"#f57542", "style":"filled", "fillcolor":"grey"})
def binary(length, outstr=""):
if len(outstr) == length:
print(outstr)
else:
for i in ["0", "1"]:
binary(length=length, outstr=outstr + i)
binary(length=3,outstr="")
vs.make_animation("binary_string.gif", delay=2)
How it works
- Base case: When
outstr reaches the desired length, print it
- Recursive case: For each position, try both ‘0’ and ‘1’
- Creates a binary tree where each level represents one bit position
- For length=3, generates all 8 binary strings: 000, 001, 010, 011, 100, 101, 110, 111
This generates 2^n strings for length n. The recursion tree has a branching factor of 2 at each level.
Make sum permutations
Find all permutations of numbers that sum to a target value:
# Author: Bishal Sarang
from visualiser.visualiser import Visualiser as vs
"""
Problemm Link: https://qr.ae/TltTCV
Find all permutations of 2, 3, and 7 that can add up to make 10. (Ex: 2,2,2,2,2; or 3,7)
Output:
[2, 2, 2, 2, 2]
[2, 2, 3, 3]
[2, 3, 2, 3]
[2, 3, 3, 2]
[3, 2, 2, 3]
[3, 2, 3, 2]
[3, 3, 2, 2]
[3, 7]
[7, 3]
"""
@vs(ignore_args=['node_num'], show_argument_name=False, show_return_value=False)
def f(sum, ans):
# If sum becoms 0 we have found the required list
if sum == 0:
print(ans)
# Include every other element to make the sum
# Number that is included also can be included
for elem in nums:
if sum - elem >= 0:
f(sum=sum - elem, ans=ans + [elem])
# We want to make the sum from list nums
nums = [2, 3, 7]
sum = 10
# Call solve with sum and an empty list
f(sum=sum, ans=[])
vs.write_image("make_sum.png")
How it works
- Base case: When sum reaches 0, a valid permutation is found
- Recursive case: Try adding each number from the list
- Numbers can be reused multiple times (unbounded)
- Explores all possible permutations, not just combinations
Notice this generates permutations (order matters), so [2,3,7] and [7,3] are both included in the output.
Missionaries and cannibals
Solve the classic missionaries and cannibals river crossing puzzle using depth-first search:
from visualiser.visualiser import Visualiser as vs
start_state = (3, 3, 1)
goal_state = (0, 0, 0)
options = [(2, 0), (1, 1), (0, 2), (1, 0), (0, 1)]
visited = dict()
def is_valid(m, c):
return m >= 0 and m <= 3 and c >= 0 and c <= 3
@vs(ignore_args=["node_num", "level"])
def dfs(m, c, s, level):
if (m, c, s) == goal_state:
return True
if m > 0 and c > m:
return False
right_side_m = 3 - m
right_side_c = 3 - c
if right_side_m > 0 and right_side_c > right_side_m:
return False
visited[(m, c, s)] = True
if s == 1:
op = -1
else:
op = 1
solved = False
for i in range(5):
next_m, next_c, next_side = m + op * options[i][0], c + op * options[i][1], int(not s)
if is_valid(next_m, next_c):
if (next_m, next_c, next_side) not in visited:
solved = (solved or dfs(m=next_m, c=next_c, s=next_side, level=level + 1))
if solved:
return True
return solved
if (dfs(m=3, c=3, s=1, level=0)):
print("SOlution Found")
# Save recursion tree to a file
vs.make_animation("missionaries.gif", delay=2)
How it works
This implements depth-first search with backtracking:
- State: (missionaries on left, cannibals on left, boat side)
- Goal: Move all missionaries and cannibals from left (1) to right (0)
- Constraints: Cannibals can never outnumber missionaries on either side
- Options: Five possible boat movements (2M, 1M1C, 2C, 1M, 1C)
- Visited tracking: Prevents revisiting the same state
This is a classic AI search problem that demonstrates:
- State space exploration
- Constraint satisfaction
- Backtracking when invalid states are reached
- Pruning with the visited dictionary
Visualization insights
The recursion tree shows:
- Valid state transitions as branches
- Invalid states (constraint violations) as dead ends
- The search path until a solution is found
- Backtracking when no valid moves exist
These advanced examples showcase how recursion visualization helps understand complex algorithms like graph search, permutation generation, and constraint satisfaction problems.