程序中递归是否都可以转化为循环？

点击上方蓝色字体，关注我们

来源于小伙伴提问。

以下是我的一些看法。

林锐博士的观点认为“所有递归都可以改写成循环”，这在计算理论上是正确的。

从图灵完备性角度来看，递归和循环是等价的——换句话说，只要一个语言具备递归或循环，它就足以表达所有可以计算的算法。

实际上，递归往往在某种程度上被编译器或解释器通过栈操作和迭代实现。

如何将递归转换为循环：递归涉及函数调用，并将每个递归调用的状态保存在函数调用栈中。要将递归转换为循环，通常需要显式地使用数据结构如栈来模拟递归调用时的状态保存。这意味着递归逻辑可以通过手动管理这些状态来模拟。

例如，计算斐波那契数列的递归实现可以很容易地转换为迭代（循环）实现。

递归版本：

int fibonacci(int n) {    if (n <= 1)        return n;    return fibonacci(n - 1) + fibonacci(n - 2);}

循环版本：

int fibonacci(int n) {    if (n <= 1)        return n;    int a = 0, b = 1, c;    for (int i = 2; i <= n; ++i) {        c = a + b;        a = b;        b = c;    }    return b;}

从这个例子看，递归确实可以转换为循环。

王垠博士的观点强调递归的表达能力比循环强。

这其实涉及到递归与循环在编程中扮演的不同角色。递归是一种更自然和直观的表示方法，尤其在处理递归数据结构时（如树、链表等），递归往往比循环更容易表达问题的本质。

例如，处理树的遍历，递归比迭代的写法更加简洁且更符合逻辑上的“分治”思想。

比如树的遍历问题，用递归表达非常自然：

void traverse(TreeNode* node) {    if (node == NULL) return;    printf("%d ", node->value);  // 先序遍历    traverse(node->left);    traverse(node->right);}

尽管可以通过栈将这个递归过程转换为循环，但代码将会更加复杂，不那么直观。像解释器、编译器等对语言的解析实现中，递归下降解析（recursive descent parsing）就是一个常见的应用。

王垠提到的一点很关键：递归更广泛，它不仅限于计算某个结果，还可以通过函数调用自身来简洁表达复杂的分解、求解问题。

尤其在处理嵌套结构或问题的递归性质时，循环可能变得冗长而不直观。

关于效率问题，林锐博士的观点认为递归效率不高，这实际上主要指尾递归优化没有被充分利用的情况下，递归确实可能导致栈空间消耗大、函数调用开销高。但如果编译器支持尾递归优化（如某些C语言编译器或Scheme等函数式语言），递归函数可以优化成和循环几乎一样的效率。

然而，递归深度过大的确可能会导致栈溢出问题，尤其是当递归深度无法事先确定时（如某些搜索算法）。

此时，尾递归无法优化的递归程序可能导致栈空间耗尽。而循环在栈上不需要保存函数调用状态，因此在处理深度很大的问题时更安全。

归根结底，递归和循环并不是非此即彼的对立关系，而是两种工具。递归在某些场景下表达能力更强，循环则在效率和空间消耗上表现出色。

用哪个更合适，取决于你面临的问题以及代码的需求。

点击阅读原文，更精彩~