是否可以在 lua 中对河内塔进行适当的尾调用？

Question

我用递归编写了一个汉诺塔问题的代码，运行它在在线 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)

我认为这可以通过适当的尾调用来解决，但据我所知，适当的尾调用必须 return 相同的函数。但是在那个代码中，递归有两个"hanoi"函数。

所以这在 lua 中是一个正确的尾调用吗？

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

有什么方法可以正确地对 hanoi 问题进行尾调用吗？

Answer 1

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

在你的例子中：

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

该函数必须 return 调用的结果，它不能使用或更改调用的结果。

在您的河内示例中，只有第二次调用可以进行尾调用，而第一次调用则不能。

是否可以在 lua 中对河内塔进行适当的尾调用？

Is it possible to make a proper tail-call of hanoi tower in lua?

lua

tail-recursion

tail-call

towers-of-hanoi