Recursion

First write it in the most natural way and especially only optimize if profiling shows it is critical.

Why recursion is often slower than iterative solutions?

Most answers here forget the obvious culprit why recursion is often slower than iterative solutions. It’s linked with the build up and tear down of stack frames but is not exactly that. It’s generally a big difference in the storage of the auto variable for each recursion. In an iterative algorithm with a loop, the variables are often held in registers and even if they spill, they will reside in the Level 1 cache. In a recursive algorithm, all intermediary states of the variable are stored on the stack, meaning they will generate many more spills to memory. This means that even if it makes the same amount of operations, it will have a lot memory accesses in the hot loop and what makes it worse, these memory operations have a lousy reuse rate making the caches less effective.

TL;DR recursive algorithms have generally a worse cache behavior than iterative ones.

Functional programming language

函数式语言是否更适合写递归？

是的，函数式语言（如 Haskell、Erlang、Scheme）天然适合递归，而命令式语言（如 C、Python、Java）通常更适合迭代。原因如下：

---

1. 函数式语言为何适合递归？

(1) 无副作用（Immutable Data）

• 函数式语言的数据默认不可变，递归时无需担心状态被修改，逻辑更纯粹。
• 示例（Haskell 计算阶乘）：

factorial 0 = 1
factorial n = n * factorial (n - 1)  -- 纯递归，无变量修改

(2) 尾递归优化（Tail Call Optimization, TCO）

• 函数式语言的编译器/解释器自动优化尾递归为循环，避免栈溢出。
• 示例（Scheme 尾递归求和）：

(define (sum n acc)
  (if (= n 0)
      acc
      (sum (- n 1) (+ acc n))))  ;; 尾递归 → 被优化为迭代

(3) 模式匹配（Pattern Matching）

• 函数式语言通过模式匹配简化递归的终止条件和分支逻辑。
• 示例（Erlang 计算斐波那契数列）：

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).  -- 递归 + 模式匹配

(4) 高阶函数支持

• map、fold、filter 等高阶函数隐藏了递归细节，开发者只需关注逻辑。
• 示例（Haskell 用 foldl 求和）：

sumList = foldl (+) 0  -- 无需手动写递归

---

2. 命令式语言为何不太适合递归？

(1) 默认不支持尾递归优化

• Python、Java、C（未优化时） 的递归深度受栈大小限制，易溢出。

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)  # 非尾递归 → 栈溢出风险

(2) 可变状态（Mutable State）

• 循环修改变量更直观，递归需额外传递状态（如累加器）。

// Java 的迭代更常见
int sum(int n) {
    int acc = 0;
    for (int i = 1; i <= n; i++) acc += i;
    return acc;
}

(3) 性能开销

• 递归的函数调用成本高于循环（压栈/弹栈操作），在性能敏感场景不占优。

---

3. 何时用递归？何时用迭代？

场景	推荐方式	示例语言
函数式编程（无副作用、TCO）	递归	Haskell、Scheme、Erlang
命令式编程（需性能、易调试）	迭代	Python、Java、C
分治算法（如快速排序）	递归 + 尾递归优化	所有语言
线性操作（如求和、遍历）	迭代	所有语言

---

4. 跨语言递归示例对比

(1) 求和（1+2+…+n）

函数式风格（Scheme）

(define (sum n acc)
  (if (= n 0)
      acc
      (sum (- n 1) (+ acc n))))  ;; 尾递归优化

命令式风格（Python）

def sum_iter(n):
    acc = 0
    while n > 0:
        acc += n
        n -= 1
    return acc

(2) 树的中序遍历

函数式风格（Haskell）

data Tree = Leaf | Node Int Tree Tree

inorder Leaf = []
inorder (Node val left right) = inorder left ++ [val] ++ inorder right

命令式风格（Java）

List<Integer> inorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        res.add(root.val);
        root = root.right;
    }
    return res;
}

---

5. 总结

• 函数式语言：递归是首选，因语言设计支持（TCO、不可变数据、模式匹配）。
• 命令式语言：优先用迭代，递归仅用于分治等特定场景（或手动优化为尾递归）。
• 通用建议：
• 如果语言支持 TCO（如 Scheme、JavaScript），可放心用递归。
• 在 Python/Java 中，递归深度大时改用迭代或尾递归 + 累加器。
• 递归的本质是“分治”，迭代的本质是“状态更新”，根据场景选择。

二级指针代替递归？

在实际开发中，是否使用二级指针（或类似技术）取决于代码可读性、维护性、性能需求和团队规范。以下是具体分析：

---

1. 二级指针的优缺点

优点：

• 精确控制内存：直接操作指针的指针，适合底层系统开发（如C/C++内核、嵌入式）。
• 避免拷贝开销：通过指针修改数据，而非传递值（如修改链表头节点）。
• 模拟栈的迭代实现：在非递归算法中替代递归调用栈（如树的迭代构建）。

缺点：

• 可读性差：二级指针容易让代码变得晦涩（如 TreeNode** parent）。
• 易出错：指针操作稍有不慎会导致悬空指针、内存泄漏。
• 语言限制：Python/Java等无显式指针的语言需用替代方案（如包装类）。

---

2. 递归 vs 二级指针迭代：如何选择？

场景	推荐方案	理由
小规模数据	递归	代码简洁，符合直觉（如树的遍历、分治算法）。
大规模数据	迭代（二级指针/栈模拟）	避免栈溢出，更可控（如处理深度超过10,000的树）。
性能敏感场景	迭代	递归的函数调用开销较高（但编译器优化后差异可能变小）。
团队协作/维护性优先	递归	递归更易读，除非明确需要避免递归（如代码规范禁止）。
无尾递归优化的语言	迭代	Python/Java等语言递归深度有限，需手动改迭代。

---

3. 各语言下的实践建议

C/C++：

• 优先递归：除非栈深度可能爆炸（如处理用户输入的巨型树）。
• 二级指针迭代示例（BST插入）：

void insert(TreeNode** root, int val) {
    while (*root) {
        root = (val < (*root)->val) ? &(*root)->left : &(*root)->right;
    }
    *root = new TreeNode(val);
}

Python/Java：

• 递归+索引传递：用子数组范围 (left, right) 替代指针。
• 迭代方案：用栈/队列+包装类（如Python的list、Java的Ref<T>）。

# Python迭代示例（无指针）
def sortedArrayToBST(nums):
    stack = [(0, len(nums)-1, None, True)]  # (left, right, parent, is_left)
    root = None
    while stack:
        left, right, parent, is_left = stack.pop()
        if left > right: continue
        mid = (left + right) // 2
        node = TreeNode(nums[mid])
        if is_left and parent: parent.left = node
        elif parent: parent.right = node
        else: root = node
        stack.append((mid+1, right, node, False))
        stack.append((left, mid-1, node, True))
    return root

Go：

• 灵活选择：Go的递归优化较好，但也可用指针的指针：

func insert(root **Node, val int) {
    for *root != nil {
        if val < (*root).val {
            root = &(*root).left
        } else {
            root = &(*root).right
        }
    }
    *root = &Node{val: val}
}

---

4. 黄金准则

1. 默认用递归：除非有明确理由（如性能、栈深度、团队规范）。
2. 二级指针迭代的适用场景：
   • 需要极致性能（如高频交易系统）。
   • 递归深度不可控（如解析用户生成的深层JSON）。
   • 语言强制要求（如某些嵌入式C环境禁用递归）。
3. 代码可读性 > 微优化：除非性能测试证明递归是瓶颈。

---

5. 经典案例参考

• Linux内核：大量使用二级指针操作链表（list_head）。
• STL库：迭代实现优先（如std::sort用迭代避免递归栈溢出）。
• Java/Python标准库：递归为主（如Collections.sort用递归TimSort）。