Lua 中如何实现汉诺塔的 proper tail-call

我用递归方式编写了一个汉诺塔问题的代码,并在在线 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)

我认为这可以通过 proper tail-call 来解决,但据我所知,proper tail-call 必须返回相同的函数。但在那个代码中,递归中有两个"hanoi"函数。


那么在 Lua 中这是一个 proper tail-call 吗?

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

是否有办法实现汉诺塔问题的 proper tail-call 呢?

点赞
用户5675002
用户5675002

适当的尾调用并不是指调用同一个函数。只要在所需条件下进行调用,就可以将对任何函数的调用视为尾调用,并且不仅限于递归。

在你的示例中:

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) -- 这个调用可以成为尾调用,只需要返回该调用的结果

        return hanoi(n-1, mid, st, dst) -- 现在这是一个适当的尾调用
    end
end

该函数必须返回调用的结果,不能使用或更改该调用的结果。

在您的hanoi示例中,只有第二个调用可以成为尾调用,而第一个无法成为尾调用。

2019-05-31 09:16:11