一步步写算法：循环与递归的本质联系与转换

核心观点

循环是递归的特例，递归与栈等价。 所有循环可改写为尾递归；所有递归可显式用栈模拟为循环。理解这一等价性，是算法设计与编程内功的关键。

1. 求和：循环 vs 递归

循环版（自底向上）

int sum_iter(int n) {
    int s = 0;
    for (int i = 1; i <= n; ++i) s += i;
    return s;
}

递归版（自顶向下）

int sum_rec(int n) {
    if (n == 0) return 0;
    return sum_rec(n - 1) + n;
}

• 循环：显式累加器 s，从 1 累加到 n。
• 递归：隐式利用调用栈保存中间状态，从 n 递减到 0 回溯累加。
• 尾递归优化：若写成 return sum_rec(n-1, acc+n)，编译器可消除栈帧，变成循环。

2. 线性查找：循环 vs 递归

// 循环
int find_iter(const int *a, int n, int v) {
    for (int i = 0; i < n; ++i) if (a[i] == v) return i;
    return -1;
}

// 递归（辅助函数隐藏索引）
int find_rec_helper(const int *a, int n, int v, int i) {
    if (i == n) return -1;
    if (a[i] == v) return i;
    return find_rec_helper(a, n, v, i + 1);
}
int find_rec(const int *a, int n, int v) {
    return find_rec_helper(a, n, v, 0);
}

递归版本引入额外参数 i 替代循环变量，本质相同。

3. 链表遍历：循环 vs 递归

struct Node { int val; Node *next; };

// 循环
void print_iter(Node *head) {
    for (Node *p = head; p; p = p->next) printf("%d ", p->val);
}

// 递归
void print_rec(Node *head) {
    if (!head) return;
    printf("%d ", head->val);
    print_rec(head->next);
}

递归极其简洁，但长链表会栈溢出。工程上单链表遍历强制用循环。

4. 显式栈模拟递归：通用模板

以二叉树后序遍历为例：

struct Frame { Node *node; int state; }; // state: 0=未访左, 1=未访右, 2=访问根
void postorder_iter(Node *root) {
    Frame st[100]; int top = 0;
    if (root) st[top++] = {root, 0};
    while (top) {
        Frame *f = &st[top-1];
        if (f->state == 0) {
            f->state = 1;
            if (f->node->left) st[top++] = {f->node->left, 0};
        } else if (f->state == 1) {
            f->state = 2;
            if (f->node->right) st[top++] = {f->node->right, 0};
        } else {
            printf("%d ", f->node->val);
            --top;
        }
    }
}

每个栈帧保存“执行到哪一步”，完美模拟递归调用栈。

5. 何时选循环，何时选递归

6. 尾调用优化 (TCO) 实战

// 非尾递归
int fact(int n) { return n == 0 ? 1 : n * fact(n-1); }

// 尾递归（累加器模式）
int fact_tail(int n, int acc) { return n == 0 ? acc : fact_tail(n-1, acc*n); }
int fact(int n) { return fact_tail(n, 1); }

GCC/Clang -O2 可将尾递归优化为跳转，栈帧常数。但 C++ 标准不保证，工程上不依赖 TCO，长递归请改循环/显式栈。

总结

• 循环 = 显式状态变量 + 跳转；递归 = 隐式调用栈 + 参数传递。
• 两者可互相机械转换：循环引入累加器/索引 → 尾递归；递归引入显式栈帧结构 → 循环。
• 掌握显式栈模拟递归通用模板，是攻克复杂非递归遍历、回溯、解释器实现的核心技能。
• 工程原则：线性结构用循环，树图分治用递归，深度不可控用显式栈。

理解循环与递归的本质统一，不再被语法形式束缚，才能在算法设计中游刃有余。