# 普通遞歸求和
def sum_recursive(n):
    if n <= 0:
        return 0
    return n + sum_recursive(n - 1)

# sum_recursive(1000)  # RecursionError!
# Python默認(rèn)遞歸深度限制為1000

import sys
print(f"默認(rèn)限制: {sys.getrecursionlimit()}")  # 1000

# 為什么有限制？
# 每次遞歸調(diào)用，Python都需要：
# 1. 在調(diào)用棧上創(chuàng)建新的棧幀
# 2. 保存局部變量和返回地址
# 3. 消耗內(nèi)存（通常每個(gè)棧幀~1KB）
# 1000層遞歸 ≈ 1MB 棧內(nèi)存
# 更深的話可能導(dǎo)致棧溢出（Stack Overflow）

# 普通遞歸——遞歸調(diào)用后還有操作（乘法）
def factorial_normal(n):
    if n <= 1:
        return 1
    return n * factorial_normal(n - 1)
    #     ↑ 遞歸調(diào)用后還要做乘法——不是尾遞歸

# 尾遞歸——遞歸調(diào)用是函數(shù)的最后一步
def factorial_tail(n, accumulator=1):
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)
    #     ↑ 遞歸調(diào)用是最后一步，結(jié)果直接返回——這是尾遞歸

# ?? 尾遞歸的優(yōu)勢(shì)：
# 編譯器和解釋器可以優(yōu)化尾遞歸——不創(chuàng)建新的棧幀
# 而是復(fù)用當(dāng)前的棧幀（因?yàn)楫?dāng)前幀已經(jīng)沒用了）
# 這意味著：尾遞歸理論上可以無限深，不會(huì)棧溢出！

# ?? 可視化對(duì)比：
def normal_recursion(n):
    """普通遞歸——調(diào)用后還有操作"""
    if n <= 0:
        return 0
    result = normal_recursion(n - 1)  # 保存result
    return n + result                  # ← 還要用n

def tail_recursion(n, acc=0):
    """尾遞歸——調(diào)用后沒有額外操作"""
    if n <= 0:
        return acc
    return tail_recursion(n - 1, acc + n)  # ← 直接返回，不需要保留n

# ?? 重要：Python官方不支持尾遞歸優(yōu)化（TCO, Tail Call Optimization）

# 即使寫成尾遞歸的形式，Python仍然會(huì)創(chuàng)建新的棧幀！
# 所以 factorial_tail(1000) 仍然會(huì)觸發(fā) RecursionError

# 為什么Python不支持？
# 1. Guido van Rossum（Python之父）認(rèn)為TCO會(huì)破壞調(diào)試信息
#    ——尾遞歸優(yōu)化會(huì)丟失調(diào)用棧的中間幀
# 2. Python的哲學(xué)："應(yīng)該只有一種明顯的方式來做一件事"
#    而迭代（循環(huán)）就是Python推薦的方式
# 3. Python的動(dòng)態(tài)特性使得TCO的實(shí)現(xiàn)復(fù)雜化

# ?? 所以結(jié)論是：
# Python中用遞歸時(shí)，要時(shí)刻注意深度限制
# 大數(shù)據(jù)量用迭代，小數(shù)據(jù)量用遞歸
# 不要指望尾遞歸優(yōu)化來救你

import sys

# 查看當(dāng)前限制
current_limit = sys.getrecursionlimit()
print(f"當(dāng)前遞歸深度限制: {current_limit}")  # 通常是1000

# 修改限制
sys.setrecursionlimit(5000)
print(f"修改后: {sys.getrecursionlimit()}")  # 5000

# ?? 警告：
# 1. 提高限制有風(fēng)險(xiǎn)——可能導(dǎo)致棧溢出導(dǎo)致Python崩潰
# 2. 操作系統(tǒng)對(duì)棧大小有限制（Windows默認(rèn)1MB，Linux默認(rèn)8MB）
# 3. 提高限制是治標(biāo)不治本——代碼邏輯才是關(guān)鍵
# 4. 恢復(fù)默認(rèn)值
sys.setrecursionlimit(1000)

# 檢查某個(gè)函數(shù)需要多深的遞歸
def measure_recursion_depth(n, current=0):
    """測(cè)量遞歸深度"""
    if n <= 0:
        return current
    return measure_recursion_depth(n - 1, current + 1)

# 安全測(cè)試
test_depths = [10, 100, 500]
for d in test_depths:
    depth = measure_recursion_depth(d)
    print(f"n=wppm3vysvbp, 實(shí)際遞歸深度={depth}")

def safe_recursive_computation(n, max_depth=900):
    """帶深度保護(hù)的遞歸計(jì)算"""
    def inner(n, depth):
        if depth > max_depth:
            raise RecursionError(f"超過安全深度限制 {max_depth}")

        if n <= 1:
            return n

        return inner(n - 1, depth + 1) + inner(n - 2, depth + 1)

    try:
        return inner(n, 0)
    except RecursionError as e:
        print(f"?? 遞歸深度超限: {e}")
        print(f"   請(qǐng)減小輸入規(guī)?；蚴褂玫姹?)
        return None

print(safe_recursive_computation(10))    # 正常
print(safe_recursive_computation(1000))  # 超限

# ?? 尾遞歸可以很自然地轉(zhuǎn)成while循環(huán)

# 尾遞歸版本
def sum_tail(n, acc=0):
    if n <= 0:
        return acc
    return sum_tail(n - 1, acc + n)

# 轉(zhuǎn)成迭代——幾乎是一一對(duì)應(yīng)的翻譯
def sum_iterative(n):
    """尾遞歸 → while循環(huán)"""
    acc = 0  # 對(duì)應(yīng)尾遞歸的accumulator
    while n > 0:  # 對(duì)應(yīng)遞歸條件
        acc = acc + n  # 更新accumulator
        n = n - 1  # 更新參數(shù)
    return acc  # 基準(zhǔn)條件的結(jié)果

print(sum_iterative(100))  # 5050

# 階乘的迭代版
def factorial_iterative(n):
    """階乘——遞歸轉(zhuǎn)迭代"""
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

print(factorial_iterative(10))  # 3628800

# 對(duì)于樹遍歷這類"自然遞歸"的問題，可以用顯式棧模擬

# 遞歸版本——二叉樹前序遍歷
class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def preorder_recursive(root):
    """遞歸版前序遍歷"""
    if root is None:
        return []
    return (
        [root.value] +
        preorder_recursive(root.left) +
        preorder_recursive(root.right)
    )

# 迭代版本——使用顯式棧
def preorder_iterative(root):
    """迭代版前序遍歷——用棧模擬遞歸"""
    if root is None:
        return []

    result = []
    stack = [root]  # 顯式維護(hù)調(diào)用棧

    while stack:
        node = stack.pop()  # "彈棧"
        result.append(node.value)

        # 先壓右，再壓左（因?yàn)闂Ｊ荓IFO）
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

# 測(cè)試
tree = TreeNode(1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, None, TreeNode(6))
)
print(preorder_recursive(tree))   # [1, 2, 4, 5, 3, 6]
print(preorder_iterative(tree))   # [1, 2, 4, 5, 3, 6]

# 斐波那契數(shù)列的三種實(shí)現(xiàn)——性能天差地別

# 版本一：樸素遞歸——O(2^n)，極慢
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# 版本二：記憶化遞歸——O(n)，很快
def fib_memoized(n, memo=None):
    """記憶化——用字典緩存已計(jì)算的結(jié)果"""
    if memo is None:
        memo = {}

    if n in memo:
        return memo[n]  # 直接返回緩存

    if n <= 1:
        return n

    memo[n] = fib_memoized(n - 1, memo) + fib_memoized(n - 2, memo)
    return memo[n]

# 版本三：迭代——O(n)，最快
def fib_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# 性能對(duì)比
import time
n = 35

start = time.perf_counter()
print(f"樸素遞歸 fib({n}) = {fib_naive(n)}")
print(f"耗時(shí): {time.perf_counter() - start:.4f}秒")
# 約1-3秒

start = time.perf_counter()
print(f"記憶化遞歸 fib({n}) = {fib_memoized(n)}")
print(f"耗時(shí): {time.perf_counter() - start:.6f}秒")
# 約0.0001秒

start = time.perf_counter()
print(f"迭代版 fib({n}) = {fib_iterative(n)}")
print(f"耗時(shí): {time.perf_counter() - start:.6f}秒")
# 約0.00001秒

from functools import lru_cache

# @lru_cache是Python官方提供的記憶化裝飾器
# 它自動(dòng)緩存函數(shù)的返回值

@lru_cache(maxsize=None)  # maxsize=None → 無限緩存
def fib_cached(n):
    """使用lru_cache的斐波那契——代碼簡(jiǎn)潔又高效"""
    if n <= 1:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)

# 計(jì)算fib(100)也不會(huì)卡！
print(fib_cached(100))  # 354224848179261915075

# 查看緩存信息
print(f"緩存信息: {fib_cached.cache_info()}")
# CacheInfo(hits=98, misses=101, maxsize=None, currsize=101)

# 清除緩存
fib_cached.cache_clear()

# lru_cache參數(shù)說明
# maxsize: 最大緩存條目數(shù)（默認(rèn)128），None表示無限制
# typed: 是否區(qū)分參數(shù)類型（例如1和1.0是否區(qū)分）

@lru_cache(maxsize=256)
def expensive_computation(x, y):
    """模擬耗時(shí)計(jì)算"""
    import time
    time.sleep(1)  # 模擬耗時(shí)
    return x * y + x + y

# 第一次調(diào)用——慢
result1 = expensive_computation(10, 20)  # 1秒

# 第二次調(diào)用相同參數(shù)——瞬間返回（命中緩存）
result2 = expensive_computation(10, 20)  # 瞬間

print(f"相同結(jié)果: {result1 == result2}")  # True

# Trampoline（蹦床）模式
# 雖然Python不支持TCO，但可以手動(dòng)模擬

# 思路：不直接在遞歸中調(diào)用，而是返回一個(gè)"描述下一步調(diào)用"的對(duì)象
# 在外部循環(huán)中執(zhí)行這些調(diào)用

def trampoline(f):
    """蹦床執(zhí)行器——處理返回的函數(shù)調(diào)用"""
    def wrapper(*args, **kwargs):
        result = f(*args, **kwargs)
        # 只要結(jié)果是可調(diào)用的，就繼續(xù)執(zhí)行
        while callable(result):
            result = result()
        return result
    return wrapper

@trampoline
def factorial_trampoline(n, acc=1):
    """使用trampoline的尾遞歸階乘"""
    if n <= 1:
        return acc
    # 不直接調(diào)用，而是返回一個(gè)lambda
    return lambda: factorial_trampoline(n - 1, n * acc)

# 現(xiàn)在可以計(jì)算大數(shù)的階乘了
print(factorial_trampoline(5))    # 120
print(factorial_trampoline(100))  # 很大的數(shù)...

# ?? trampoline模式在實(shí)踐中很少使用——太繞了
# 大多數(shù)情況下，直接把遞歸轉(zhuǎn)成迭代更簡(jiǎn)單