Python Tail Recursion Concept Practice Problems & Exercises
Practice: Tail Recursion Concept
← Back to lessonEasy
Classify each function below as tail-recursive or not. Fill in the classify function to return the correct label for each.
# Examine each function and determine: is the recursive call the LAST operation?
def a(n):
if n == 0: return 0
return a(n - 1)
def b(n, acc=0):
if n == 0: return acc
return b(n - 1, acc + n)
def c(n):
if n == 0: return 0
return n + c(n - 1)
def d(lst):
if not lst: return []
return [lst[0] * 2] + d(lst[1:])
def e(n):
if n <= 1: return 1
return e(n - 1) + e(n - 2)
def classify(name, is_tail):
return f"{name}: {'tail-recursive' if is_tail else 'NOT tail-recursive'}"
# Fill in True or False for each function
print(classify("a", True))
print(classify("b", True))
print(classify("c", False))
print(classify("d", False))
print(classify("e", False))Solution
def a(n):
if n == 0: return 0
return a(n - 1)
def b(n, acc=0):
if n == 0: return acc
return b(n - 1, acc + n)
def c(n):
if n == 0: return 0
return n + c(n - 1)
def d(lst):
if not lst: return []
return [lst[0] * 2] + d(lst[1:])
def e(n):
if n <= 1: return 1
return e(n - 1) + e(n - 2)
def classify(name, is_tail):
return f"{name}: {'tail-recursive' if is_tail else 'NOT tail-recursive'}"
print(classify("a", True)) # return a(n-1) — nothing after the call
print(classify("b", True)) # return b(n-1, acc+n) — acc+n computed BEFORE the call
print(classify("c", False)) # n + c(n-1) — addition AFTER the call returns
print(classify("d", False)) # [lst[0]*2] + d(lst[1:]) — concatenation AFTER the call
print(classify("e", False)) # e(n-1) + e(n-2) — addition of TWO recursive calls
Key insight: In b, the expression acc + n is computed before the recursive call is made (it becomes an argument). The recursive call itself is the last operation. In c, the addition n + result happens after c(n-1) returns — making it non-tail.
For e (Fibonacci), there are two recursive calls. Even if one were a tail call, the other cannot be — the results must be added together.
Expected Output
a: tail-recursive\nb: tail-recursive\nc: NOT tail-recursive\nd: NOT tail-recursive\ne: NOT tail-recursiveHints
Hint 1: A recursive call is a tail call only if it is the LAST operation — nothing happens with its return value.
Hint 2: If there is addition, multiplication, list concatenation, or any other operation AFTER the recursive call returns, it is NOT a tail call.
The non-tail recursive sum_list adds the head to the result of recursing on the tail. Convert it to a tail-recursive version sum_list_tail using an accumulator parameter.
# Non-tail recursive: n + sum_list(rest) — addition AFTER recursive call
def sum_list(lst):
if not lst:
return 0
return lst[0] + sum_list(lst[1:])
# TODO: Convert to tail-recursive using an accumulator
def sum_list_tail(lst, acc=0):
if not lst:
return acc
return sum_list_tail(lst[1:], acc + lst[0])
print(f"Non-tail sum: {sum_list([1, 2, 3, 4, 5])}")
print(f"Tail sum: {sum_list_tail([1, 2, 3, 4, 5])}")
print(f"Empty sum: {sum_list_tail([])}")Solution
def sum_list(lst):
if not lst:
return 0
return lst[0] + sum_list(lst[1:])
def sum_list_tail(lst, acc=0):
if not lst:
return acc
return sum_list_tail(lst[1:], acc + lst[0])
print(f"Non-tail sum: {sum_list([1, 2, 3, 4, 5])}")
print(f"Tail sum: {sum_list_tail([1, 2, 3, 4, 5])}")
print(f"Empty sum: {sum_list_tail([])}")
Trace of sum_list_tail([1, 2, 3, 4, 5]):
sum_list_tail([1,2,3,4,5], 0)
sum_list_tail([2,3,4,5], 1) # acc = 0 + 1
sum_list_tail([3,4,5], 3) # acc = 1 + 2
sum_list_tail([4,5], 6) # acc = 3 + 3
sum_list_tail([5], 10) # acc = 6 + 4
sum_list_tail([], 15) # acc = 10 + 5
-> 15
The key transformation: instead of head + recursive_result, we pass acc + head as the new accumulator. The recursive call is now the last operation — no pending addition after it returns.
Expected Output
Non-tail sum: 15\nTail sum: 15\nEmpty sum: 0Hints
Hint 1: The accumulator carries the running total. Each recursive call adds the current element to it.
Hint 2: The base case returns the accumulator (not 0), because the accumulator already holds the final answer.
Write a tail-recursive function reverse_tail that reverses a list using an accumulator. The accumulator builds the reversed list by prepending each element.
def reverse_tail(lst, acc=None):
if acc is None:
acc = []
if not lst:
return acc
return reverse_tail(lst[1:], [lst[0]] + acc)
print(f"Reversed: {reverse_tail([1, 2, 3, 4, 5])}")
print(f"Reversed: {reverse_tail(['a', 'b', 'c'])}")
print(f"Reversed: {reverse_tail([])}")Solution
def reverse_tail(lst, acc=None):
if acc is None:
acc = []
if not lst:
return acc
return reverse_tail(lst[1:], [lst[0]] + acc)
print(f"Reversed: {reverse_tail([1, 2, 3, 4, 5])}")
print(f"Reversed: {reverse_tail(['a', 'b', 'c'])}")
print(f"Reversed: {reverse_tail([])}")
Trace of reverse_tail([1, 2, 3]):
reverse_tail([1, 2, 3], [])
reverse_tail([2, 3], [1]) # acc = [1] + [] = [1]
reverse_tail([3], [2, 1]) # acc = [2] + [1] = [2, 1]
reverse_tail([], [3, 2, 1]) # acc = [3] + [2, 1] = [3, 2, 1]
-> [3, 2, 1]
Why acc=None instead of acc=[]: Default mutable arguments in Python are shared across calls. Using acc=[] would mean the same list object is reused, leading to bugs. The None sentinel pattern avoids this.
Expected Output
Reversed: [5, 4, 3, 2, 1]\nReversed: ['c', 'b', 'a']\nReversed: []Hints
Hint 1: Prepend each head element to the accumulator list as you recurse through the input.
Hint 2: Start with an empty accumulator. Each step: `acc = [lst[0]] + acc` or `acc = [head] + acc`.
Convert the standard recursive factorial to a tail-recursive version using an accumulator.
# Non-tail recursive: n * factorial(n-1)
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
# TODO: Tail-recursive version with accumulator
def factorial_tail(n, acc=1):
if n <= 1:
return acc
return factorial_tail(n - 1, acc * n)
print(f"factorial(5) = {factorial_tail(5)}")
print(f"factorial(10) = {factorial_tail(10)}")
print(f"factorial(0) = {factorial_tail(0)}")
print(f"factorial(1) = {factorial_tail(1)}")Solution
def factorial_tail(n, acc=1):
if n <= 1:
return acc
return factorial_tail(n - 1, acc * n)
print(f"factorial(5) = {factorial_tail(5)}")
print(f"factorial(10) = {factorial_tail(10)}")
print(f"factorial(0) = {factorial_tail(0)}")
print(f"factorial(1) = {factorial_tail(1)}")
Trace of factorial_tail(5):
factorial_tail(5, 1)
factorial_tail(4, 5) # acc = 1 * 5 = 5
factorial_tail(3, 20) # acc = 5 * 4 = 20
factorial_tail(2, 60) # acc = 20 * 3 = 60
factorial_tail(1, 120) # acc = 60 * 2 = 120
-> 120
The pattern: Move the "work after the call" into an accumulator argument passed into the call. n * factorial(n-1) becomes factorial_tail(n-1, acc * n). The multiplication now happens before the recursive call, not after.
Expected Output
factorial(5) = 120\nfactorial(10) = 3628800\nfactorial(0) = 1\nfactorial(1) = 1Hints
Hint 1: The accumulator starts at 1 (the multiplicative identity). Each step multiplies acc by n, then decrements n.
Hint 2: Compare: non-tail is `n * factorial(n-1)` — multiplication after the call. Tail is `factorial_tail(n-1, acc * n)` — multiplication before the call (as an argument).
Medium
Implement a trampoline function and a trampolined count_down that can handle depths far beyond Python's recursion limit. The count_down function should return "done" when it reaches 0.
def trampoline(func, *args):
result = func(*args)
while callable(result):
result = result()
return result
def count_down(n):
if n == 0:
return "done"
return lambda: count_down(n - 1)
print(f"Countdown result: {trampoline(count_down, 10)}")
print(f"Deep countdown result: {trampoline(count_down, 50000)}")Solution
def trampoline(func, *args):
result = func(*args)
while callable(result):
result = result()
return result
def count_down(n):
if n == 0:
return "done"
return lambda: count_down(n - 1)
print(f"Countdown result: {trampoline(count_down, 10)}")
print(f"Deep countdown result: {trampoline(count_down, 50000)}")
How it works step by step:
trampoline(count_down, 3):
result = count_down(3) -> returns lambda (not "done")
result = result() -> calls lambda -> count_down(2) -> returns lambda
result = result() -> calls lambda -> count_down(1) -> returns lambda
result = result() -> calls lambda -> count_down(0) -> returns "done"
"done" is not callable -> return "done"
Stack depth at any point: 2 frames — the trampoline loop and the current count_down call. The lambda is created and returned, so count_down(n) exits before count_down(n-1) is called. No accumulation of frames.
Expected Output
Countdown result: done\nDeep countdown result: doneHints
Hint 1: Instead of calling `count_down(n-1)` directly, return a lambda that calls it: `lambda: count_down(n-1)`. This prevents a new stack frame from being created.
Hint 2: The trampoline function is a while loop that keeps calling the result as long as it is callable. When the result is not callable, it is the final answer.
Combine the accumulator pattern with the trampoline to compute factorials for very large n without hitting the recursion limit.
def trampoline(func, *args):
result = func(*args)
while callable(result):
result = result()
return result
def factorial_t(n, acc=1):
if n <= 1:
return acc
return lambda: factorial_t(n - 1, acc * n)
def factorial(n):
return trampoline(factorial_t, n)
print(f"factorial(5) = {factorial(5)}")
print(f"factorial(20) = {factorial(20)}")
result = factorial(5000)
print(f"factorial(5000) has {len(str(result))} digits")Solution
def trampoline(func, *args):
result = func(*args)
while callable(result):
result = result()
return result
def factorial_t(n, acc=1):
if n <= 1:
return acc
return lambda: factorial_t(n - 1, acc * n)
def factorial(n):
return trampoline(factorial_t, n)
print(f"factorial(5) = {factorial(5)}")
print(f"factorial(20) = {factorial(20)}")
result = factorial(5000)
print(f"factorial(5000) has {len(str(result))} digits")
Why this works for n=5000:
Without the trampoline, factorial(5000) would create 5000 stack frames and crash with RecursionError (default limit is 1000). With the trampoline, the stack depth stays at 2 regardless of n.
Performance note: The trampoline adds overhead from creating a lambda object at each step. For production Python code, a simple while loop is faster:
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
The trampoline is useful when the algorithm's recursive structure is complex enough that converting to a loop would obscure the logic.
Expected Output
factorial(5) = 120\nfactorial(20) = 2432902008176640000\nfactorial(5000) has 16326 digitsHints
Hint 1: Combine the accumulator pattern with the trampoline: `factorial_t(n, acc)` returns a lambda when n > 1, and returns `acc` (the final answer) when n <= 1.
Hint 2: The trampoline loop keeps calling thunks until it gets a non-callable result (the integer answer).
Convert the recursive power function to an iterative version. The recursive version computes base^exp by multiplying base by the result of power(base, exp - 1). Your iterative version should use a loop.
# Recursive version (crashes for exp > 1000)
def power_recursive(base, exp):
if exp == 0:
return 1
return base * power_recursive(base, exp - 1)
# TODO: Convert to iterative
def power(base, exp):
result = 1
for _ in range(exp):
result *= base
return result
print(f"power(2, 10) = {power(2, 10)}")
print(f"power(3, 5) = {power(3, 5)}")
print(f"power(5, 0) = {power(5, 0)}")
print(f"power(7, 1) = {power(7, 1)}")
print(f"power(2, 20) = {power(2, 20)}")Solution
def power(base, exp):
result = 1
for _ in range(exp):
result *= base
return result
print(f"power(2, 10) = {power(2, 10)}")
print(f"power(3, 5) = {power(3, 5)}")
print(f"power(5, 0) = {power(5, 0)}")
print(f"power(7, 1) = {power(7, 1)}")
print(f"power(2, 20) = {power(2, 20)}")
The conversion pattern:
Recursive: Iterative:
base case -> return 1 result = 1 (initial value)
recursive: base * f(exp-1) loop exp times: result *= base
returns after all calls unwind returns result directly
Why iterative is better here:
- Recursive: O(exp) stack frames, crashes at exp > 1000
- Iterative: O(1) stack space, handles any exp value
- For even better performance, use exponentiation by squaring: O(log exp) multiplications
# Bonus: fast power via repeated squaring
def fast_power(base, exp):
result = 1
while exp > 0:
if exp % 2 == 1:
result *= base
base *= base
exp //= 2
return result
Expected Output
power(2, 10) = 1024\npower(3, 5) = 243\npower(5, 0) = 1\npower(7, 1) = 7\npower(2, 20) = 1048576Hints
Hint 1: The recursive version does `base * power(base, exp - 1)`. The iterative version uses a loop that multiplies `result` by `base` on each iteration.
Hint 2: Initialize `result = 1` and multiply by `base` exactly `exp` times.
The naive recursive Fibonacci has exponential time complexity and crashes for moderate n. Convert it to an iterative version that uses two state variables (a, b) to track consecutive Fibonacci numbers.
def fib(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(n - 1):
a, b = b, a + b
return b
print(f"fib(0) = {fib(0)}")
print(f"fib(1) = {fib(1)}")
print(f"fib(10) = {fib(10)}")
print(f"fib(50) = {fib(50)}")
print(f"fib(100) = {fib(100)}")Solution
def fib(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(n - 1):
a, b = b, a + b
return b
print(f"fib(0) = {fib(0)}")
print(f"fib(1) = {fib(1)}")
print(f"fib(10) = {fib(10)}")
print(f"fib(50) = {fib(50)}")
print(f"fib(100) = {fib(100)}")
How a, b = b, a + b works:
Step 0: a=0, b=1 (fib(0), fib(1))
Step 1: a=1, b=1 (fib(1), fib(2))
Step 2: a=1, b=2 (fib(2), fib(3))
Step 3: a=2, b=3 (fib(3), fib(4))
Step 4: a=3, b=5 (fib(4), fib(5))
...
Python evaluates the right side (b, a + b) BEFORE assigning to the left side (a, b). This is simultaneous assignment — no temporary variable needed.
Comparison:
Naive recursive: O(2^n) time, O(n) stack — fib(50) takes minutes
Memoized recursive: O(n) time, O(n) stack — fib(1000) hits recursion limit
Iterative: O(n) time, O(1) space — fib(100000) runs in seconds
Expected Output
fib(0) = 0\nfib(1) = 1\nfib(10) = 55\nfib(50) = 12586269025\nfib(100) = 354224848179261915075Hints
Hint 1: Track two variables: `a` (fib(i-1)) and `b` (fib(i)). Each step: `a, b = b, a + b` advances by one position.
Hint 2: This is equivalent to the accumulator pattern with two accumulators — one for each of the two preceding Fibonacci values.
Hard
Implement Fibonacci using the trampoline pattern with two accumulators. This should handle fib(10000) without stack overflow.
def trampoline(func, *args):
result = func(*args)
while callable(result):
result = result()
return result
def _fib(n, a=0, b=1):
if n == 0:
return a
if n == 1:
return b
return lambda: _fib(n - 1, b, a + b)
def fib(n):
return trampoline(_fib, n)
print(f"fib(0) = {fib(0)}")
print(f"fib(1) = {fib(1)}")
print(f"fib(10) = {fib(10)}")
print(f"fib(100) = {fib(100)}")
result = fib(10000)
print(f"fib(10000) has {len(str(result))} digits")Solution
def trampoline(func, *args):
result = func(*args)
while callable(result):
result = result()
return result
def _fib(n, a=0, b=1):
if n == 0:
return a
if n == 1:
return b
return lambda: _fib(n - 1, b, a + b)
def fib(n):
return trampoline(_fib, n)
print(f"fib(0) = {fib(0)}")
print(f"fib(1) = {fib(1)}")
print(f"fib(10) = {fib(10)}")
print(f"fib(100) = {fib(100)}")
result = fib(10000)
print(f"fib(10000) has {len(str(result))} digits")
Trace of fib(5) via trampoline:
trampoline(_fib, 5):
_fib(5, 0, 1) -> lambda # n=5, a=0, b=1
_fib(4, 1, 1) -> lambda # n=4, a=1, b=1
_fib(3, 1, 2) -> lambda # n=3, a=1, b=2
_fib(2, 2, 3) -> lambda # n=2, a=2, b=3
_fib(1, 3, 5) -> 5 # n=1, return b=5
Why two accumulators: Standard Fibonacci needs two preceding values. A single accumulator only carries one value. By threading both a (fib(i)) and b (fib(i+1)), we can compute the next pair in a single tail call: _fib(n-1, b, a+b) advances from (fib(i), fib(i+1)) to (fib(i+1), fib(i+2)).
Expected Output
fib(0) = 0\nfib(1) = 1\nfib(10) = 55\nfib(100) = 354224848179261915075\nfib(10000) has 2090 digitsHints
Hint 1: Use two accumulators: `a` (current fib value) and `b` (next fib value). Each "step" returns a lambda that calls `_fib(n-1, b, a+b)`.
Hint 2: The base cases: when n == 0 return `a`, when n == 1 return `b`. These are plain values (not lambdas), which stops the trampoline loop.
Implement tree_sum_cps that sums all values in a binary tree using Continuation-Passing Style (CPS) combined with a trampoline. In CPS, instead of returning a result, each function passes it to a continuation (callback). This converts tree recursion (two recursive calls) into a chain of tail calls.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def trampoline(func, *args):
result = func(*args)
while callable(result):
result = result()
return result
def _tree_sum(node, cont):
if node is None:
return lambda: cont(0)
# CPS: sum left, then in its continuation sum right, then combine
def after_left(left_sum):
def after_right(right_sum):
return lambda: cont(node.val + left_sum + right_sum)
return lambda: _tree_sum(node.right, after_right)
return lambda: _tree_sum(node.left, after_left)
def tree_sum(root):
return trampoline(_tree_sum, root, lambda x: x)
# 4
# / \
# 2 6
# / \ / \
# 1 3 5 7
tree = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
print(f"Tree sum: {tree_sum(tree)}")
# Build a deep left-skewed tree: 1 + 2 + ... + 200 + 100*1990
def build_deep_tree(n):
if n == 0:
return None
node = Node(n)
current = node
for i in range(n - 1, 0, -1):
current.left = Node(i)
current = current.left
return node
deep = build_deep_tree(200)
# Add a chain to make it deeper
current = deep
while current.left:
current = current.left
for i in range(1990):
current.left = Node(100)
current = current.left
print(f"Deep tree sum: {tree_sum(deep)}")Solution
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def trampoline(func, *args):
result = func(*args)
while callable(result):
result = result()
return result
def _tree_sum(node, cont):
if node is None:
return lambda: cont(0)
def after_left(left_sum):
def after_right(right_sum):
return lambda: cont(node.val + left_sum + right_sum)
return lambda: _tree_sum(node.right, after_right)
return lambda: _tree_sum(node.left, after_left)
def tree_sum(root):
return trampoline(_tree_sum, root, lambda x: x)
tree = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
print(f"Tree sum: {tree_sum(tree)}")
deep = build_deep_tree(200)
current = deep
while current.left:
current = current.left
for i in range(1990):
current.left = Node(100)
current = current.left
print(f"Deep tree sum: {tree_sum(deep)}")
How CPS converts tree recursion to a tail-call chain:
Normal recursion (two recursive calls — NOT tail recursive):
def tree_sum(node):
if node is None: return 0
return node.val + tree_sum(node.left) + tree_sum(node.right)
^ ^
Two pending operations after each call!
CPS transformation (single chain of tail calls):
_tree_sum(node, cont):
1. Sum left subtree, passing a continuation that will:
2. Sum right subtree, passing a continuation that will:
3. Combine node.val + left_sum + right_sum and pass to original cont
Each step returns a lambda (thunk), so the trampoline executes them one at a time with constant stack depth. The continuations (closures) are heap-allocated, so they do not consume stack space.
Trade-off: CPS is powerful but harder to read. For production code, an iterative approach with an explicit stack is usually clearer:
def tree_sum_iter(root):
total = 0
stack = [root]
while stack:
node = stack.pop()
if node:
total += node.val
stack.append(node.left)
stack.append(node.right)
return total
Expected Output
Tree sum: 28\nDeep tree sum: 199990Hints
Hint 1: Continuation-Passing Style (CPS) adds an extra parameter — a function (the "continuation") — that receives the result instead of returning it directly.
Hint 2: For a tree with left and right children: first sum the left subtree, passing a continuation that then sums the right subtree and adds both to the node value.
Build a reusable @trampolined decorator that lets you write tail-recursive functions naturally. The decorator should use a TailCall sentinel class (not callable check) to distinguish "continue recursing" from "return this value." This avoids the bug where returning an actual callable value (like a function) would be mistaken for a thunk.
class TailCall:
"""Sentinel that holds the next function call to make."""
def __init__(self, func, *args, **kwargs):
self.func = func
self.args = args
self.kwargs = kwargs
def trampolined(func):
"""Decorator: wraps func so recursive self-calls return TailCall objects."""
def wrapper(*args, **kwargs):
result = func(*args, **kwargs)
while isinstance(result, TailCall):
result = result.func(*result.args, **result.kwargs)
return result
# Attach TailCall creator so the function can signal "recurse"
wrapper.call = lambda *args, **kwargs: TailCall(func, *args, **kwargs)
return wrapper
@trampolined
def count_down(n):
if n == 0:
return "done"
return count_down.call(n - 1)
@trampolined
def factorial(n, acc=1):
if n <= 1:
return acc
return factorial.call(n - 1, acc * n)
@trampolined
def fib(n, a=0, b=1):
if n == 0:
return a
if n == 1:
return b
return fib.call(n - 1, b, a + b)
print(f"count_down(100000) = {count_down(100000)}")
result_f = factorial(5000)
print(f"factorial(5000) has {len(str(result_f))} digits")
result_fib = fib(10000)
print(f"fib(10000) has {len(str(result_fib))} digits")Solution
class TailCall:
"""Sentinel that holds the next function call to make."""
def __init__(self, func, *args, **kwargs):
self.func = func
self.args = args
self.kwargs = kwargs
def trampolined(func):
"""Decorator: wraps func so recursive self-calls return TailCall objects."""
def wrapper(*args, **kwargs):
result = func(*args, **kwargs)
while isinstance(result, TailCall):
result = result.func(*result.args, **result.kwargs)
return result
wrapper.call = lambda *args, **kwargs: TailCall(func, *args, **kwargs)
return wrapper
@trampolined
def count_down(n):
if n == 0:
return "done"
return count_down.call(n - 1)
@trampolined
def factorial(n, acc=1):
if n <= 1:
return acc
return factorial.call(n - 1, acc * n)
@trampolined
def fib(n, a=0, b=1):
if n == 0:
return a
if n == 1:
return b
return fib.call(n - 1, b, a + b)
print(f"count_down(100000) = {count_down(100000)}")
result_f = factorial(5000)
print(f"factorial(5000) has {len(str(result_f))} digits")
result_fib = fib(10000)
print(f"fib(10000) has {len(str(result_fib))} digits")
Why TailCall sentinel instead of callable check:
Problem with callable check:
def get_handler(name):
if name == "done":
return lambda x: x # Legitimate return value!
return lambda: get_handler(name[1:]) # Thunk for trampoline
trampoline would call the returned lambda — BUG!
Solution with TailCall sentinel:
@trampolined
def get_handler(name):
if name == "done":
return lambda x: x # Not a TailCall — returned as-is
return get_handler.call(name[1:]) # TailCall object — trampoline continues
Design decisions:
wrapper.callcreates aTailCallwithout executing the function — this is how the decorated function signals "tail-recurse with these args."isinstance(result, TailCall)is unambiguous — no collision with callable return values.- The trampoline loop is inside
wrapper, so the user just callsfactorial(5000)naturally. **kwargssupport means keyword arguments work too.
This pattern is production-quality. Libraries like fn.py and toolz use similar approaches.
Expected Output
count_down(100000) = done\nfactorial(5000) has 16326 digits\nfib(10000) has 2090 digitsHints
Hint 1: Create a `TailCall` wrapper class that holds the function and arguments for the next call. The trampoline loop checks `isinstance(result, TailCall)` instead of `callable(result)` — this avoids the problem of legitimate callable return values.
Hint 2: The decorator wraps the function so that calling it returns a `TailCall` object. A separate `execute` or `run` function drives the trampoline loop.