Recursion and tail calls
A recursive function calls itself, and a tail call lets it do so without growing the stack.
In this page:
Recursion and tail calls
A recursive function must be declared with local function so that its name is visible inside its own body. Each call uses stack space, so very deep recursion overflows. A call of the form return f(x) is a proper tail call in Lua and does not consume extra stack, so loops can be written as tail recursion.
Note:
With local f = function ... end the name f is not yet visible inside the body, so use local function or declare first.
Example: Recursion and tail calls
local function fact(n)
if n <= 1 then return 1 end
return n * fact(n - 1)
end
print(fact(5), fact(20))
local function sumTo(n, acc)
acc = acc or 0
if n == 0 then return acc end
return sumTo(n - 1, acc + n)
end
print(sumTo(100000))
-- Output:
-- 120 2432902008176640000
-- 5000050000Login to try C/C++/Java/PHP code in the editor
Common Mistakes
- Writing local f = function and calling f inside it
- Forgetting the base case
- Adding work after the recursive call and losing the tail call
Chapter Summary
- Use local function for recursion
- A base case stops recursion
- return f(x) is a tail call
- Tail calls do not grow the stack
🔒
Chapter Quiz — Complete all 7 topics to unlock
0/7 topics done
Complete these topics first: