Tail Call Optimization (TCO)

-- -----------------------------------------------
-- Basic tail call syntax
-- -----------------------------------------------

-- Tail call: the last operation of the function must be in the form return f(...)
local function funcName(arg)
    -- processing
    return anotherFunc(arg)   -- this is a tail call (does not consume the stack)
end

-- -----------------------------------------------
-- Example that is NOT a tail call (consumes the stack)
-- -----------------------------------------------

local function nonTail(n)
    return nonTail(n - 1) + 1  -- there is an operation after the return, so this is NOT a tail call
end

-- -----------------------------------------------
-- Correct form of tail recursion
-- -----------------------------------------------

local function tailRecursion(n, acc)
    if n == 0 then return acc end
    return tailRecursion(n - 1, acc + n)  -- last operation is return f() only -> TCO applies
end

Pattern	Description
return f(args)	The most basic tail call. TCO applies when the last statement of a function is in the form return f(...).
return f(args) + 1 (non-TCO)	When an operation is added to the return value, it is no longer a tail call. Stack frames accumulate.
Accumulator pattern	Passing the intermediate computation result as an argument (accumulator) converts regular recursion into tail call form.
State machine	Define each state as a function and express transitions as return nextState(). No stack is consumed regardless of recursion depth.
Infinite loop via tail call	Instead of while true do end, you can express an infinite loop with return self(). No stack overflow occurs.
Mutual recursion	TCO also applies when function A tail-calls function B, and B tail-calls A.

dragonball_tail_call.lua

-- dragonball_tail_call.lua — tail call optimization sample
-- Uses Dragon Ball characters to demonstrate TCO behavior

-- -----------------------------------------------
-- 1. Tail recursion with the accumulator pattern
-- -----------------------------------------------
-- Accumulates Son Goku's power levels one at a time.
-- Normal recursion would cause a stack overflow for large n,
-- but converting to tail recursion with the accumulator pattern avoids it.

local function sum_power(n, acc)
    if n == 0 then
        return acc
    end
    return sum_power(n - 1, acc + n)  -- tail call: does not consume the stack
end

-- No stack overflow even with 100,000 recursive calls
local total = sum_power(100000, 0)
print("=== Accumulator Pattern ===")
print("Son Goku total power (1 to 100000): " .. total)
print("")

-- -----------------------------------------------
-- 2. State machine (battle phase management)
-- -----------------------------------------------
-- Expresses battle phases against Frieza as functions.
-- Each phase tail-calls the next, so no stack is consumed regardless of phase count.

-- phase_start tail-calls phase_scouter, phase_transform tail-calls phase_final.
-- Because the callee is defined later, forward declarations as local variables are needed.
local phase_scouter
local phase_final

local function phase_start(log)
    table.insert(log, "Frieza battle: start")
    return phase_scouter(log)           -- tail call
end

local function phase_transform(log)
    table.insert(log, "Frieza: 1st form -> transforms to Final Form")
    return phase_final(log)             -- tail call
end

phase_scouter = function(log)
    table.insert(log, "Son Goku: measuring Frieza's power with a scouter")
    return phase_transform(log)         -- tail call
end

phase_final = function(log)
    table.insert(log, "Son Goku: awakens as a Super Saiyan!")
    table.insert(log, "Frieza defeated!")
    return log
end

local battle_log = phase_start({})
print("=== Battle Phases (State Machine) ===")
for i, entry in ipairs(battle_log) do
    print("  " .. i .. ". " .. entry)
end
print("")

-- -----------------------------------------------
-- 3. Infinite loop via tail call (simulated event loop)
-- -----------------------------------------------
-- Implements Vegeta's training count with tail recursion.
-- Uses return self() instead of while.

local function vegeta_train(count, limit, log)
    if count > limit then
        return log
    end
    table.insert(log, "Vegeta: training session " .. count .. " complete (Power +" .. count * 1000 .. ")")
    return vegeta_train(count + 1, limit, log)  -- tail recursion: stack does not grow
end

local train_log = vegeta_train(1, 5, {})
print("=== Repetition via Tail Recursion ===")
for _, entry in ipairs(train_log) do
    print("  " .. entry)
end
print("")

-- -----------------------------------------------
-- 4. Mutual recursion (Son Gohan and Piccolo alternating training)
-- -----------------------------------------------
-- gohan and piccolo tail-call each other.
-- TCO also applies to mutual recursion.

local piccolo_teach  -- forward declaration

local function gohan_train(round, max, log)
    if round > max then return log end
    table.insert(log, "Round " .. round .. ": Son Gohan training...")
    return piccolo_teach(round, max, log)   -- tail call to Piccolo
end

piccolo_teach = function(round, max, log)
    table.insert(log, "Round " .. round .. ": Piccolo instructing")
    return gohan_train(round + 1, max, log) -- tail call to Gohan
end

local mutual_log = gohan_train(1, 3, {})
print("=== Mutual Recursion (Son Gohan and Piccolo) ===")
for _, entry in ipairs(mutual_log) do
    print("  " .. entry)
end
print("")

-- -----------------------------------------------
-- 5. Verifying TCO: extremely deep recursion
-- -----------------------------------------------
-- Normal recursion would cause a stack overflow after a few thousand calls,
-- but tail recursion can handle millions without issue.

local function countdown(n)
    if n == 0 then return "Summon the Dragon Balls!" end
    return countdown(n - 1)  -- tail call
end

local result = countdown(1000000)  -- 1 million tail recursive calls
print("=== Deep Tail Recursion (1 million calls) ===")
print("  " .. result)

lua dragonball_tail_call.lua
=== Accumulator Pattern ===
Son Goku total power (1 to 100000): 5000050000

=== Battle Phases (State Machine) ===
  1. Frieza battle: start
  2. Son Goku: measuring Frieza's power with a scouter
  3. Frieza: 1st form -> transforms to Final Form
  4. Son Goku: awakens as a Super Saiyan!
  5. Frieza defeated!

=== Repetition via Tail Recursion ===
  Vegeta: training session 1 complete (Power +1000)
  Vegeta: training session 2 complete (Power +2000)
  Vegeta: training session 3 complete (Power +3000)
  Vegeta: training session 4 complete (Power +4000)
  Vegeta: training session 5 complete (Power +5000)

=== Mutual Recursion (Son Gohan and Piccolo) ===
  Round 1: Son Gohan training...
  Round 1: Piccolo instructing
  Round 2: Son Gohan training...
  Round 2: Piccolo instructing
  Round 3: Son Gohan training...
  Round 3: Piccolo instructing

=== Deep Tail Recursion (1 million calls) ===
  Summon the Dragon Balls!

Common Mistake 1: Not knowing that an operation after return prevents TCO

A tail call must be in the form return f(args). When an operation is added to the return value, such as return f(args) + 1 or return f(args) .. "x", TCO does not apply and the stack accumulates.

ng_example.lua

-- Looks like a tail call but is not (there is an operation after return)
local function bad_sum(n)
    if n == 0 then return 0 end
    return bad_sum(n - 1) + n  -- TCO does not apply
end

-- stack overflow with deep recursion
local ok, err = pcall(bad_sum, 1000000)
print(ok, err)

false	stack overflow

Convert to a tail call using the accumulator pattern.

ok_example.lua

local function good_sum(n, acc)
    if n == 0 then return acc end
    return good_sum(n - 1, acc + n)  -- tail call: TCO applies
end

local result = good_sum(1000000, 0)
print(result)

500000500000

Common Mistake 2: Storing the result in a variable before returning does not qualify as TCO

The form local x = f(args); return x, where the result is stored in a variable before being returned, is not a tail call. You must write return f(args) directly.

ng_example2.lua

local function count_down(n)
    if n == 0 then return "done" end
    local result = count_down(n - 1)  -- storing in a variable first
    return result                      -- TCO does not apply
end

local ok, err = pcall(count_down, 1000000)
print(ok, err)

false	stack overflow

Writing return f(args) directly applies TCO.

ok_example2.lua

local function count_down(n)
    if n == 0 then return "done" end
    return count_down(n - 1)  -- direct return: TCO applies
end

local result = count_down(1000000)
print(result)

done

"Tail call optimization (TCO)" is an optimization where, when the last operation of a function is a call to another function, the current stack frame is replaced with the new frame rather than added on top of it, consuming no stack. Lua guarantees this as part of its language specification: any form of return f(args) always has TCO applied.

The conditions for TCO are strict: only the return f(args) form qualifies. Cases like return f(args) + 1 (operation after the return value) or local x = f(args); return x (variable-based return) are not eligible for TCO.

The most commonly used pattern is the "accumulator pattern." The normal recursion return n + sum(n-1) is not a tail call, but by passing the intermediate value as an argument, it can be converted to the tail call form return sum(n-1, acc+n). This is also effective for implementing state machines, where each state is defined as a function and transitions are expressed as return nextState(), allowing state transitions to be written without worrying about recursion depth. TCO also applies to mutual recursion (function A tail-calls B, B tail-calls A). For more, also see the Recursive Functions and Function Basics pages.