# ===== CodeLab: 递归与分治思想 =====
# 来源: https://aoerliang.dpdns.org/articles/algo-recursion
# 以下代码片段按文章出现顺序拼接, 共 4 段

# ----- 片段 1 (python) -----
def factorial(n):
    if n <= 1:          # 基线条件
        return 1
    return n * factorial(n - 1)  # 缩小规模,信任递归结果

print(factorial(5))   # 120

# ----- 片段 2 (python) -----
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def inorder(root):      # 中序遍历:左 → 根 → 右
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

root = TreeNode(1)   # 根为 1,左右孩子 2、3
root.left = TreeNode(2)
root.right = TreeNode(3)
print(inorder(root))   # [2, 1, 3]

# ----- 片段 3 (python) -----
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

# fib(45) 要跑几十秒:同一个子问题被反复计算

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_fast(n):
    if n <= 1:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

print(fib_fast(100))  # 瞬间完成

# ----- 片段 4 (python) -----
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    i = j = 0
    res = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    return res + a[i:] + b[j:]

print(merge_sort([5, 1, 4, 2, 8]))  # [1, 2, 4, 5, 8]