Recursion in Lua
Implement recursive algorithms and understand Lua's tail-call optimization.
What is Recursion?
Recursion is when a function calls itself to solve a smaller instance of the same problem. Every recursive function needs a base case (where it stops) and a recursive case (where it reduces the problem). Without a base case, recursion causes a stack overflow.
local function countdown(n)
if n <= 0 then
print("Blast off!")
return
end
print(n)
countdown(n - 1)
end
countdown(5)
-- 5, 4, 3, 2, 1, Blast off!Factorial
Factorial is the classic recursion example: n! = n × (n-1)! with base case 0! = 1. Each call reduces n by 1 until reaching the base case. The results "unwind" back up the call stack, multiplying as they go.
local function factorial(n)
if n <= 1 then return 1 end
return n * factorial(n - 1)
end
print(factorial(1)) -- 1
print(factorial(5)) -- 120
print(factorial(10)) -- 3628800