Approach: Replace direct recursive calls with thunks (zero-arg functions that capture the next step) and use a trampoline runner that repeatedly invokes thunks in a loop. This flattens control from the language call stack to the heap, avoiding stack overflow in languages without tail-call optimization.Example: depth-first backtracking that finds one solution for combination sum.python
# Pseudocode / Python-style trampoline runner
def trampoline(thunk):
# Loop until a non-callable (final result) is produced
while callable(thunk):
thunk = thunk()
return thunk
# Original recursive backtracking (conceptual)
# def backtrack(i, state):
# if base_case: return result
# for choice in choices:
# apply choice
# res = backtrack(next_i, new_state)
# if res: return res
# return None
# Trampolined version: every recursive step returns a thunk
def backtrack_tr(i, state, target):
# Return a thunk or final result
def step():
if target_reached(state, target):
return state # final result (not callable)
if i >= len(items):
return None
for choice in choices_for(i):
new_state = apply(choice, state)
# Instead of calling recursively, return a thunk that continues
result = backtrack_tr(i+1, new_state, target)
# If result is callable, we must return a thunk that when executed will evaluate it
if callable(result):
return lambda result=result: trampoline(result)
if result:
return result
return None
return step
# Use:
initial_thunk = backtrack_tr(0, initial_state, target)
solution = trampoline(initial_thunk)
