2

我用递归制作了一个河内塔问题的代码，并在在线lua编译器上运行它。如果我将输入超过 14，它就不会运行。

local num = io.read("*n")
local count = 0
function hanoi(n, st, mid, dst)
    if n == 1 then
        count = count + 1
        print(st, dst)
    else
        hanoi(n-1, st, dst, mid)
        count = count + 1
        print(st, dst)
        hanoi(n-1, mid, st, dst)
    end
end

hanoi(num, 1, 2, 3)
print(count)

我认为这可以通过适当的尾调用来解决，但据我所知，正确的尾调用必须返回相同的函数。但在该代码中，递归中有两个“hanoi”函数。

那么这是 lua 中正确的尾调用吗？

function f(args)
    return f(args_1), f(args_2)
end

有没有办法对河内问题进行适当的尾声？

4

1 回答 1

2

正确的尾调用不是调用相同的函数。如果该调用在所需条件下发生，则对任何函数的调用都将是尾调用，并且不限于递归。

在您的示例中：

function hanoi(n, st, mid, dst)
    if n == 1 then
        count = count + 1
        print(st, dst)
    else
        hanoi(n-1, st, dst, mid) -- you continue after this call,
                                 -- possibly expecting the result, this call
                                 -- can't be a proper tail call
        count = count + 1
        print(st, dst)

        hanoi(n-1, mid, st, dst) -- this call can be made a tail call,
                                 -- just return the result of that call

        return hanoi(n-1, mid, st, dst) -- now this is a proper tail call
    end
end

函数必须返回调用的结果，它不能使用或改变调用的结果。

在您的 hanoi 示例中，只有第二个电话可以作为尾电话，但不能是第一个电话。

于 2019-05-31T09:16:11.613 回答