Можно ли сделать правильный вызов из Ханойской башни в Луа? - PullRequest
Новая
       37

Можно ли сделать правильный вызов из Ханойской башни в Луа?

2 голосов
/ 31 мая 2019

Я сделал код башни Ханойской проблемы с рекурсией и запустил ее на онлайн-компиляторе 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)

Я думаю, что это можно решить с помощью правильного хвостового вызова, но, насколько мне известно, правильный хвостовой вызов должен возвращать ту же функцию.Но в этом коде есть две функции "Ханоя" в рекурсивном.

Так что это правильный вызов хвоста в lua? 

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

И есть лиспособ сделать правильный вызов из Ханоя проблемы?

1 Ответ

2 голосов
/ 31 мая 2019

Правильный хвостовой вызов не связан с вызовом одной и той же функции. Вызов любой функции будет хвостовым, если этот вызов происходит при требуемых условиях и не ограничивается рекурсиями.

В вашем примере: 

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

Функция должна возвращать результат вызова, она не должна использовать или изменять результат вызова.

В вашем примере с Ханое можно сделать только второй вызов, но не первый.

...