Lua Academy · Lesson

Recursion in Lua

Implement recursive algorithms and understand Lua's tail-call optimization.

Recursion in Lua is a free Lua Academy lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Lua Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

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

Fibonacci

The Fibonacci sequence is another classic: fib(n) = fib(n-1) + fib(n-2). Naive recursion is exponential — it recomputes the same values repeatedly. We'll see memoization as a fix, but first the basic form.

local function fib(n)
  if n <= 1 then return n end
  return fib(n - 1) + fib(n - 2)
end

for i = 0, 10 do
  io.write(fib(i) .. " ")
end
print()
-- 0 1 1 2 3 5 8 13 21 34 55

Memoized Recursion

Memoization caches previously computed results in a table. On each call, check the cache first. If the value is there, return it immediately. Otherwise, compute and store it. This turns exponential-time Fibonacci into linear time.

local memo = {}
local function fib(n)
  if memo[n] then return memo[n] end
  if n <= 1 then return n end
  local result = fib(n-1) + fib(n-2)
  memo[n] = result
  return result
end

print(fib(40))  -- 102334155  (fast!)

Tail Call Optimization

Lua performs tail call optimization (TCO): when the last action of a function is a call to another function, Lua reuses the current stack frame. This makes tail-recursive functions use O(1) stack space. Not all recursion is tail-recursive — the call must be the last thing in the function.

-- Tail-recursive factorial using accumulator
local function factTail(n, acc)
  acc = acc or 1
  if n <= 1 then return acc end
  return factTail(n - 1, n * acc)  -- tail call
end

print(factTail(10))  -- 3628800
-- Can handle very large n without stack overflow

Tree Traversal

Recursion naturally expresses tree traversal. A tree is a table with value, left, and right fields. Preorder, inorder, and postorder traversals differ only in when the value is processed relative to the recursive calls.

local function inorder(node)
  if node == nil then return end
  inorder(node.left)
  io.write(node.value .. " ")
  inorder(node.right)
end

local tree = {
  value=4,
  left={value=2, left={value=1}, right={value=3}},
  right={value=6, left={value=5}, right={value=7}}
}
inorder(tree)  -- 1 2 3 4 5 6 7

Mutual Recursion

Two functions can call each other (mutual recursion). In Lua, you need forward declarations: declare local variables first, then assign the functions. This way each function can reference the other's variable, which is already in scope.

local isEven, isOdd

isEven = function(n)
  if n == 0 then return true end
  return isOdd(n - 1)
end

isOdd = function(n)
  if n == 0 then return false end
  return isEven(n - 1)
end

print(isEven(10))  -- true
print(isOdd(7))    -- true

Recursive Deep Copy

Recursion is ideal for operations on nested structures. Deep copying a table means copying its contents and recursively copying any nested tables (so modifying the copy doesn't affect the original).

local function deepCopy(orig)
  local copy
  if type(orig) == "table" then
    copy = {}
    for k, v in pairs(orig) do
      copy[deepCopy(k)] = deepCopy(v)
    end
    setmetatable(copy, getmetatable(orig))
  else
    copy = orig
  end
  return copy
end

local a = {1, {2, 3}}
local b = deepCopy(a)
b[2][1] = 99
print(a[2][1])  -- 2 (unchanged)

Flood Fill Algorithm

Flood fill (used in paint programs and game maps) is naturally recursive. Starting from a cell, mark it, then recursively fill each unvisited neighbor. The recursion terminates when it hits boundaries or already-visited cells.

local grid = {
  {0,0,0,1,0},
  {0,1,0,1,0},
  {0,1,1,1,0},
  {0,0,0,0,0},
}

local function fill(g, r, c)
  if r<1 or r>#g or c<1 or c>#g[r] then return end
  if g[r][c] ~= 0 then return end
  g[r][c] = 2  -- mark visited
  fill(g,r-1,c); fill(g,r+1,c)
  fill(g,r,c-1); fill(g,r,c+1)
end

fill(grid, 1, 1)
print(grid[1][1], grid[2][1])  -- 2  2

Stack Depth Awareness

Lua's default call stack is limited (typically ~200 levels for non-tail calls). Deep non-tail recursion causes a "stack overflow" error. Solutions: convert to tail recursion, use an explicit stack (table), or use coroutines for large iterative tasks.

-- Simulate deep recursion danger
local function depth(n)
  if n == 0 then return "done" end
  return depth(n - 1)  -- tail call, safe
end
print(depth(100000))  -- done  (tail call, no overflow)

-- Non-tail: limited depth
local function countDown(n)
  if n == 0 then return 0 end
  return 1 + countDown(n - 1)  -- NOT a tail call
end
-- countDown(10000) would stack overflow

Quick Check

Which of the following is a proper tail call in Lua?

Recap: Recursion

Summary:

Every recursive function needs a base case and a recursive case
Tail calls (last action is a call) are optimized by Lua — O(1) stack
Memoization converts exponential recursion to linear
Mutual recursion requires forward declarations
Deep recursion on trees/graphs is natural; watch stack depth for non-tail calls

Frequently asked questions

Is the “Recursion in Lua” lesson free?

Yes — the full text of “Recursion in Lua” is free to read here on the web, and the Lua Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Lua Academy course, upgrade to CoddyKit PRO.

What will I learn in “Recursion in Lua”?

Implement recursive algorithms and understand Lua's tail-call optimization. You practise Lua Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start Lua Academy?

No prior experience is required. Lua Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Recursion in Lua” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this Lua Academy lesson?

Yes. Every Lua Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

← Back to Lua Academy