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

Question

I made a code of tower of hanoi problem with recursion and run it on the online lua compiler. If I put the input over 14, it didn't run.

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)

I think this can be solved by proper tail-call, but in my knowledge the proper tail call must return the same function. But in that code, there are two "hanoi" function in recursive.

So is this a proper tail call in lua?

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

And is there any way to make proper tail call of hanoi problem?

score 2 · Accepted Answer · answered May 31 '19 at 09:16

The proper tail call is not about calling the same function. The call to any function would be a tail call if that call happens under required conditions, and it's not limited to recursions.

In your example:

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

The function must return the result of the call, it must not use or alter the result of the call.

In your hanoi example only the second call can be made a tail call, but not the first one.

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

1 Answers1