// CPython 内部结构（简化）
typedef struct _frame {
    PyObject_VAR_HEAD
    struct _frame *f_back;      // 指向上一个栈帧
    PyCodeObject *f_code;       // 指向代码对象
    PyObject *f_locals;         // 局部变量字典
    PyObject **f_valuestack;    // 值栈底
    Py_ssize_t f_stackdepth;    // 当前栈深度
    int f_lineno;               // 当前行号
} PyFrameObject;

import sys
print(sys.getrecursionlimit())  # 默认 1000
sys.setrecursionlimit(3000)     # 可调大，但小心栈溢出

def countdown(n):
    # 基线条件
    if n <= 0:
        return
    print(n)
    # 递归条件（向基线逼近：n → n-1）
    countdown(n - 1)

# ❌ 缺失基线条件 → RecursionError
def infinite(n):
    return infinite(n + 1)

# ❌ 不向基线逼近 → 也是无限递归
def bad_fact(n):
    if n == 0:
        return 1
    return n * bad_fact(n)  # 没有减小 n

# 非尾递归 — 需要保存 n，返回后再乘
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)  # 最后操作是乘，不是递归

# 尾递归形式 — 不需要保存额外状态
def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, n * acc)  # 最后操作就是递归

# 尾递归版本
def fact_tail(n, acc=1):
    if n == 0:
        return acc
    return fact_tail(n - 1, n * acc)

# 等价迭代版本
def fact_iter(n):
    acc = 1
    while n > 0:
        acc = n * acc
        n -= 1
    return acc

def trampoline(f):
    """将尾递归函数转换为迭代执行"""
    def wrapped(*args, **kwargs):
        result = f(*args, **kwargs)
        while callable(result):
            result = result()
        return result
    return wrapped

def fact_trampoline(n, acc=1):
    if n == 0:
        return acc
    # 返回一个 lambda 而非调用自身
    return lambda: fact_trampoline(n - 1, n * acc)

fact_trampoline = trampoline(fact_trampoline)
print(fact_trampoline(10000))  # ✅ 不会栈溢出！

# 深度 1001 → RecursionError
recurse(1000)  # 刚好在边界
recurse(1001)  # 💥 RecursionError: maximum recursion depth exceeded

# fib(5) 计算 fib(3) 两次，fib(2) 三次...
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

# fib(40) 需要约 3.3 亿次调用！

# ❌ 共享同一个列表！
def traverse(node, visited=[]):
    visited.append(node)
    for child in node.children:
        traverse(child, visited)

# ✅ 使用 None 并创建新列表
def traverse(node, visited=None):
    if visited is None:
        visited = []
    visited.append(node)
    ...

def factorial(n, depth=0):
    prefix = "  " * depth
    print(f"{prefix}factorial({n}) called")
    if n == 0:
        print(f"{prefix}→ return 1")
        return 1
    result = n * factorial(n - 1, depth + 1)
    print(f"{prefix}→ return {result}")
    return result

# 输出：
# factorial(3) called
#   factorial(2) called
#     factorial(1) called
#       factorial(0) called
#       → return 1
#     → return 1
#   → return 2
# → return 6

import sys

# 检查当前限制
print(sys.getrecursionlimit())  # 默认 1000

# 安全增加（不要超过系统栈大小）
sys.setrecursionlimit(10_000)

# ⚠️ 增大限制不是银弹：
# - 超过了系统 C 栈限制会导致 Segfault（段错误）
# - 更深的递归 = 更大的内存消耗
# - 更好的做法：改成迭代

def trace_calls(func):
    """装饰器：追踪递归调用次数和参数"""
    def wrapper(*args, **kwargs):
        wrapper.call_count += 1
        return func(*args, **kwargs)
    wrapper.call_count = 0
    return wrapper

@trace_calls
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

fib(10)
print(f"fib(10) 被调用了 {fib.call_count} 次")
# 输出: fib(10) 被调用了 177 次

from functools import lru_cache

# 基础版：O(2ⁿ) — fib(40) ≈ 3.3 亿次调用
def fib_naive(n):
    if n <= 1: return n
    return fib_naive(n-1) + fib_naive(n-2)

# 记忆化版：O(n) — fib(40) 仅 41 次调用
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)

# 手动实现 memoization（理解原理）
def make_memoized(func):
    cache = {}
    def memoized(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return memoized

@make_memoized
def fib_manual(n):
    if n <= 1: return n
    return fib_manual(n-1) + fib_manual(n-2)