トランポリンは末尾再帰をループに変換し、スタックオーバーフローを防ぐ手法です。Python は末尾再帰最適化をしないため、深い再帰にはこの技法が有効です。
問題の再確認
def factorial(n, acc=1): if n <= 1: return acc return factorial(n - 1, acc * n) factorial(10000) # RecursionError
末尾再帰の形でも、Python ではスタックを消費します。
トランポリンの仕組み
関数が直接再帰呼び出しする代わりに、「次に呼び出すべき関数」を返します。トランポリン関数がこれをループで実行します。
class Thunk: def __init__(self, func, *args, **kwargs): self.func = func self.args = args self.kwargs = kwargs def trampoline(func, *args, **kwargs): result = func(*args, **kwargs) while isinstance(result, Thunk): result = result.func(*result.args, **result.kwargs) return result
トランポリン対応の階乗
def factorial_t(n, acc=1): if n <= 1: return acc return Thunk(factorial_t, n - 1, acc * n) result = trampoline(factorial_t, 10000) print(len(str(result))) # 35660 桁
RecursionError なしで計算できます。
デコレータ化
def trampolined(func): def wrapper(*args, **kwargs): result = func(*args, **kwargs) while isinstance(result, Thunk): result = result.func(*result.args, **result.kwargs) return result return wrapper @trampolined def fib_t(n, a=0, b=1): if n == 0: return a return Thunk(fib_t, n - 1, b, a + b) print(fib_t(10000)) # 巨大なフィボナッチ数
ジェネレータを使った方法
def trampoline_gen(gen): stack = [gen] result = None while stack: try: item = stack[-1].send(result) if hasattr(item, "__next__"): stack.append(item) result = None else: result = item except StopIteration as e: stack.pop() result = e.value return result
トランポリンは再帰的アルゴリズムを Python で安全に実行する実用的なパターンです。
