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?
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.