3

I've had this question on my mind for a really long time but I can't figure out the answer. The question is, if does every recursive function have an iterative function that does the same?

For example,

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

This can be easily rewritten iteratively:

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

But there are many other, more complicated recursive functions, so I don't know the answer in general. This might also be a theoretical computer science question.

4

2 回答 2

2

是的，从理论的角度来看，递归函数总是可以写成迭代——这在之前已经讨论过。引用链接的帖子：

因为您可以使用严格的迭代结构构建图灵完备语言，而仅使用递归结构构建图灵完备语言，因此两者是等价的。

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

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

于 2013-09-06T16:59:32.707 回答
0

不去理论，很容易说服自己任何递归函数都可以通过观察处理器（例如奔腾）只是迭代运行而具有迭代等价物。

于 2013-09-10T18:18:17.657 回答