递归 vs 迭代：两种思维，一个目标

说实话，递归和迭代这个话题，我每次带新人都会聊一遍。很多人觉得递归很酷，迭代很土。但真正写代码久了你会发现——没有银弹。每种方法都有自己的脾气。

今天我就跟你聊聊，什么时候该用递归，什么时候老老实实用循环。以及，这两者之间的性能与可读性博弈。

先看一个简单例子：阶乘

咱们先写两段代码，感受一下区别。

// 递归版
int factorial_recursive(int n) {
    if (n <= 1) return 1;
    return n * factorial_recursive(n - 1);
}

// 迭代版
int factorial_iterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

你看，递归版只有三行，逻辑清晰。迭代版也不复杂，但多了个循环变量。嗯，这里要注意——递归的简洁，是有代价的。

递归的代价：函数调用不是免费的

每次递归调用，系统都要做三件事：

• 压栈：保存当前函数的局部变量和返回地址
• 跳转：跳到被调函数执行
• 返回：执行完后恢复现场

我曾在项目中遇到过一个问题：用递归遍历一个深度为 10000 的树结构，结果程序直接崩了。为什么？栈溢出了。每个递归调用大概消耗 16 字节的栈空间，10000 层就是 160KB。听起来不大？但别忘了，主线程的栈默认只有 1MB 左右。再加上其他局部变量，很容易就爆了。

什么时候用递归？

我个人习惯，在以下场景优先考虑递归：

1. 问题天然具有递归结构——比如树的遍历、图的深度优先搜索、分治算法（快速排序、归并排序）
2. 代码可读性要求高——递归版本往往更接近数学定义，别人一看就懂
3. 递归深度可控——比如二叉树的高度通常不会超过 logN，安全

举个例子，遍历一个二叉树：

void traverse_tree(TreeNode* node) {
    if (node == NULL) return;
    printf("%d ", node->val);
    traverse_tree(node->left);
    traverse_tree(node->right);
}

你想想看，如果用迭代写这个，你得手动维护一个栈。代码量翻倍不说，还容易出错。递归在这里就是天然的选择。

什么时候用循环？

反过来，这些场景我建议你老老实实用循环：

1. 递归深度可能很大——比如处理一个链表、或者深度不确定的树
2. 性能敏感——循环没有函数调用开销，速度更快
3. 尾递归优化不可靠——虽然 C 标准没强制要求尾递归优化，但很多编译器会做。不过，依赖编译器优化总归不踏实

说白了，如果你不确定递归深度，或者对性能有硬性要求，那就用循环。比如遍历一个单链表：

void traverse_list(ListNode* head) {
    ListNode* cur = head;
    while (cur != NULL) {
        printf("%d ", cur->val);
        cur = cur->next;
    }
}

这个用递归也能写，但没必要。链表可能很长，递归深度不可控，何必冒险？

性能对比：到底差多少？

我做过一个简单的测试，计算 n=30 的斐波那契数列：

方法	耗时（微秒）	栈空间
递归（无优化）	约 1200	O(n)
迭代	约 0.3	O(1)
尾递归（开启优化）	约 0.4	O(1)

看到了吗？递归比迭代慢了三个数量级。为什么会这样？因为递归做了大量重复计算。斐波那契的递归实现，时间复杂度是 O(2^n)，而迭代是 O(n)。

可读性 vs 性能：怎么权衡？

我个人的经验是：先写对，再写快。在大多数业务代码中，可读性比性能更重要。因为代码是写给人看的，机器只是顺便执行。

但如果你在写底层库、驱动、或者嵌入式代码，那性能就是第一位的。这时候，哪怕递归写起来更优雅，我也会选择迭代。

知识体系：递归 vs 迭代全景图

下面这张图，帮你快速理清两者的关系：

总结一下

递归和迭代，没有绝对的好坏。我的建议是：

• 递归：适合树、图、分治等天然递归结构，深度可控时优先使用
• 迭代：适合线性结构、深度不确定、性能敏感的场景
• 权衡：先保证代码正确和可读，再考虑性能优化

嗯，最后说一句：别迷信递归，也别排斥它。工具而已，用对地方才是高手。

---