recursion - 每个递归函数都可以重写为迭代函数吗？

Question

这个问题我想了很久，但就是想不出答案。问题是，是否每个递归函数都有一个具有相同功能的迭代函数？

例如，

factorial(n) {
    if (n==1) { return 1 }
    else      { return factorial(n-1) }
}

这可以很容易地迭代重写:

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

但是还有许多其他更复杂的递归函数，所以我一般不知道答案。这也可能是一个理论计算机科学问题。

Answer 1

是的，从理论的角度来看，递归函数总是可以写成迭代 - 这已经被讨论过 before 。引用链接帖子:

Because you can build a Turing complete language using strictly iterative structures and a Turning complete language using only recursive structures, then the two are therefore equivalent.

解释一下:我们知道任何可计算的问题都可以通过图灵机来解决。并且可以构造一种无需递归的编程语言A，相当于图灵机。同样，可以构建一种无需迭代的编程语言 B，其计算能力与图灵机相同。

因此，如果A和B都是Turing-complete我们可以得出结论，对于任何迭代程序，都必须存在等效的递归程序，反之亦然。这是一个理论结果，从某种意义上说，它没有给您任何关于如何从任意迭代程序派生一个递归程序的提示，反之亦然。