每个迭代函数都可以转化为递归函数吗？

Question

现在一些编译器可以帮助我们将递归函数转换为迭代函数，但我的问题是每个迭代函数都可以有一个递归函数吗？

Answer 1

每个迭代函数都可以转换为递归函数，反之亦然。丘奇-图灵假说认为图灵机是一个通用计算系统：任何可计算函数都可以作为图灵机来实现。如果您的语言可以实现图灵机，那么它就是图灵机等价的，因此可以计算任何可计算函数。

我们可以使用递归而不进行迭代来实现图灵机吗？当然可以

TuringMachine(tape[1...n...], head, state)
    if state = halt_accept then return true
    if state = halt_reject then return false
    (t, h, s) = RunTransition(tape[head], state)
    tape[head] = t
    return TuringMachine(tape, h, s)

函数

RunTransition

只是检查转换表中当前磁带符号和状态的匹配行，并返回新的磁带符号、磁带头位置和状态。这应该说明，原则上，递归对于实现图灵机来说是完全足够的，这意味着任何可计算的函数都可以通过递归来解决（如果你相信丘奇-图灵假设）。因为迭代函数不能比图灵机做得更多（同样，如果你接受丘奇图灵假设），那么任何迭代过程都可以变成递归过程。

For 循环并不难想象：

function Foo()
    for i = 1 to n
        f(i)
Foo()

... becomes ...

function Foo(i)
    f(i)
    if i + 1 < n then foo(i + 1)

Foo(0)

While 循环也进行类似转换：

function Foo()
    condition = true
    while condition
        f()

Foo()

... becomes ...

Foo()
    if condition then
        f()
        Foo()

Foo()