PythonTrampoline与递归优化

# Python Trampoline 与递归优化 —— 打破递归限制
# Python 不支持尾递归优化，Trampoline 模式将递归转化为循环

import sys
from functools import wraps, partial

# 1. 递归限制问题
def factorial_recursive(n):
"""普通递归阶乘，受限于调用栈深度"""
if n <= 1: return 1
return n * factorial_recursive(n - 1)

print("默认递归限制:", sys.getrecursionlimit())
try:
factorial_recursive(2000)
except RecursionError as e:
print("递归超出限制:", e)

# 2. Trampoline 基础模式
def trampoline(func):
"""蹦床函数：反复调用返回的函数直到返回非函数值"""
result = func
while callable(result):
result = result()
return result

def factorial_trampoline(n, acc=1):
"""蹦床版阶乘 —— 返回函数而非递归调用"""
if n <= 1: return acc
return lambda: factorial_trampoline(n - 1, n * acc)

print("蹦床阶乘(10):", trampoline(factorial_trampoline(10)))
print("蹦床阶乘(5000) 位数:", len(str(trampoline(factorial_trampoline(5000)))))

# 3. 通用蹦床装饰器
def trampoline_decorator(func):
"""自动将递归函数转换为栈安全版本"""
@wraps(func)
def wrapper(*args, **kwargs):
result = func(*args, **kwargs)
while callable(result):
result = result()
return result
return wrapper

@trampoline_decorator
def even(n):
"""判断偶数（相互递归）"""
return True if n == 0 else lambda: odd(n - 1)

@trampoline_decorator
def odd(n):
"""判断奇数（与 even 相互递归）"""
return False if n == 0 else lambda: even(n - 1)

print("1000 是偶数?", even(1000))
print("100000 是偶数?", even(100000)) # 栈安全

# 4. 使用 partial 实现蹦床（比 lambda 更高效）
@trampoline_decorator
def fibonacci(n, a=0, b=1):
"""斐波那契数列的蹦床版本"""
if n == 0: return a
if n == 1: return b
return partial(fibonacci, n - 1, b, a + b)

print("斐波那契(10):", fibonacci(10))
print("斐波那契(100):", fibonacci(100))

# 5. 递归转迭代（显式栈）
def tree_depth_iterative(root):
"""树的深度计算 —— 使用显式栈替代递归"""
if root is None: return 0
stack = [(root, 1)]
max_depth = 0
while stack:
node, depth = stack.pop()
if node is not None:
max_depth = max(max_depth, depth)
if hasattr(node, 'right'):
stack.append((node.right, depth + 1))
if hasattr(node, 'left'):
stack.append((node.left, depth + 1))
return max_depth

class TreeNode:
def __init__(self, v, left=None, right=None):
self.value = v; self.left = left; self.right = right

tree = TreeNode(1,
TreeNode(2, TreeNode(4)),
TreeNode(3, None, TreeNode(5, None, TreeNode(6))))
print("树深度（迭代）:", tree_depth_iterative(tree))

# 6. 三种技术对比
"""
sys.setrecursionlimit() —— 临时提升限制，治标不治本
Trampoline —— 保持递归风格，但每次"弹跳"有函数调用开销
递归转迭代 —— 性能最优，但代码复杂度增加
"""
import time

def bench(desc, func):
start = time.perf_counter()
result = func()
print(f"{desc}: {result}, 耗时 {time.perf_counter()-start:.4f}s")

def fib_iterative(n):
"""迭代版斐波那契（最高效）"""
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a

bench("蹦床fib(1000)", lambda: trampoline(fibonacci(1000)))
bench("迭代fib(1000)", lambda: fib_iterative(1000))