递归与迭代实现互转疑问：所有迭代版本都存在对应递归实现吗？

答案是完全可以，理论和实践层面都没有障碍。

核心依据 #

迭代和递归对应的计算模型算力完全等价：迭代对应图灵机的执行模式，递归对应λ演算的执行模式，二者已经被证明计算能力完全对等，不存在只能用其中一种实现的逻辑。

通用转换方法 #

转换逻辑非常固定，你只需要做三步：

• 把原迭代逻辑里用到的所有循环可变变量（计数器、累加器、中间状态变量等）全部改成递归函数的入参
• 把原循环的终止条件，改成递归的终止边界，满足条件时直接返回结果
• 每次递归调用时，按照原循环里的变量更新规则，传入新的参数值即可

举个最简单的迭代求阶乘的例子：

int factorial_iter(int n) {
    int result = 1;
    for(int i=1; i<=n; i++) {
        result *= i;
    }
    return result;
}

按照上面的规则转递归，一行都不用多写：

int factorial_recur(int n, int result) {
    if(n == 1) return result;
    return factorial_recur(n-1, result * n);
}
// 对外暴露的调用入口，不需要传初始累加值
int factorial(int n) {
    return factorial_recur(n, 1);
}

补充说明 #

• 上面的递归写法属于尾递归，也就是递归调用是函数执行的最后一步，支持尾递归优化的运行环境会把这种递归直接优化成和迭代完全一样的执行逻辑，不会有额外的栈开销，也不会出现栈溢出问题。
• 实际开发中很少有人主动把迭代转递归，只是因为没必要：大部分命令式语言的迭代写法可读性更好，也不需要考虑部分环境不支持尾递归优化导致的栈溢出问题，只有纯函数式编程语言（比如Haskell）因为没有原生循环语法，才会默认用递归实现所有迭代逻辑。

内容的提问来源于stack exchange，提问作者Madhav Chittlangia