Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 32 ยท Functions

Recursion and Tail Calls

Write recursive Lua functions, avoid the local function trap, see why proper tail calls never overflow the stack, and speed up recursion with memoization.

A recursive function is one that calls itself. It is the natural way to describe problems that contain smaller copies of themselves: a factorial, a folder that contains folders, a tree whose branches are trees. Every recursive function needs two parts: a base case that answers directly, and a recursive case that moves closer to the base case.

Lua adds two things worth knowing. One is a small scoping rule that decides whether a function can see its own name. The other is proper tail calls, a guarantee that some recursive calls use no extra stack at all. Lua is not installed on this site, so the Lua listings are read-only and the runnable examples are JavaScript stand-ins, including a small trick that imitates tail calls, because JavaScript does not have them.

A first recursive function

The factorial of n is n * (n-1) * ... * 1, and the factorial of 0 is 1. As a recursive function:

LUA
local function factorial(n)
  if n <= 1 then
    return 1                    -- base case
  end
  return n * factorial(n - 1)   -- recursive case
end

print(factorial(5))    --> 120
print(factorial(20))   --> 2432902008176640000

Lua 5.4 integers are 64-bit, so factorial(20) is exact, and factorial(21) wraps around to a wrong (negative) number. If you call factorial(21.0) with a float, you get an approximate float result instead. See Numbers and the math Library for integer and float details.

Why local function matters

Look carefully at how the function was defined. local function factorial(n) ... end is not the same as local factorial = function(n) ... end. The first form is translated into this:

LUA
local factorial
factorial = function(n)
  -- the body can see the local variable "factorial"
end

The local variable is created before the function body, so the body can refer to it. In the second form, the variable is created after the whole right-hand side has been evaluated, so inside the body the name factorial means a global that does not exist:

LUA
local fact = function(n)
  if n <= 1 then return 1 end
  return n * fact(n - 1)    -- "fact" here is a global, which is nil
end

print(fact(3))   -- error: attempt to call a nil value (global 'fact')

This is the most common recursion mistake in Lua. Always write local function name, or declare the variable on its own line first (local fact then fact = function ... end).

Recursion with data: a nested list

Recursion shines on nested structures. This function adds up numbers inside lists that may contain other lists:

LUA
local function deepSum(item)
  if type(item) == "number" then
    return item
  end
  local total = 0
  for _, child in ipairs(item) do
    total = total + deepSum(child)
  end
  return total
end

print(deepSum({1, {2, 3}, {4, {5}}}))   --> 15

The base case is a plain number. The recursive case sums the children, and each child may itself be a list.

Two parts of every recursion

Base case Answers without calling itself.
Recursive case Calls itself on a smaller input.

No base case means no end.

1 / 2

Stack depth

Each normal call needs a bit of memory, called a stack frame, to remember where to continue. A recursion that goes very deep can use up the stack. Lua then raises a stack overflow error instead of crashing, which pcall can catch (see Error Handling). The limit is generous, around a million stack slots in the standard Lua 5.4, so ordinary recursion depths of thousands are fine. A function with no base case, or one that is fed a huge input, will hit it:

LUA
local function forever(n)
  return 1 + forever(n + 1)   -- never stops, and work remains after each call
end

print(pcall(forever, 1))      --> false   (an error message mentioning stack overflow)

Proper tail calls

A tail call is a call that is the last thing a function does, written exactly as return f(args). Because nothing remains to be done after it returns, Lua does not need the old frame any more. It reuses it. Lua guarantees this (the manual calls them proper tail calls), so a tail-recursive loop can run forever without growing the stack.

Compare two ways of summing 1 to n:

LUA
-- Not a tail call: after sumTo(n-1) returns, we still add n
local function sumTo(n)
  if n == 0 then return 0 end
  return n + sumTo(n - 1)
end

-- Tail call: the recursive call is the whole return value
local function sumAcc(n, acc)
  if n == 0 then return acc end
  return sumAcc(n - 1, acc + n)
end

print(sumAcc(1000000, 0))   --> 500000500000

sumAcc carries its running total in an extra accumulator parameter, so when it reaches the end it can just hand the answer back. A million calls use constant stack space. sumTo(1000000) would use a frame per call and is a likely stack overflow.

Watch out for things that look like tail calls but are not: return n * f(n-1) (a multiplication remains), return f(x), 1 (more values follow) and return (f(x)) (the parentheses force a single value, so the result must be adjusted). Only the plain return f(x) counts. Tail calls also work between different functions, which makes state machines easy: each state ends by tail-calling the next one.

Try it: tail calls with a trampoline

JavaScript engines do not guarantee tail-call elimination, so deep recursion overflows there. The stand-in below shows the idea Lua implements internally. A trampoline runs a loop: instead of calling itself, the function returns a small "call this next" object, and the loop does the calling, using no extra stack.

JS Tail calls via a trampoline (JavaScript)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Memoization

Some recursions repeat work. The naive Fibonacci function recomputes the same values exponentially many times. Memoization stores each result in a table the first time it is computed:

LUA
local memo = {}

local function fib(n)
  if n <= 2 then
    return 1
  end
  if memo[n] then
    return memo[n]            -- already known
  end
  local value = fib(n - 1) + fib(n - 2)
  memo[n] = value
  return value
end

print(fib(50))   --> 12586269025

Without the table, fib(50) would take billions of calls. With it, each value from 3 to 50 is computed once. The memo table is an upvalue of fib, so it persists between calls; if you keep it inside a function, the result is a reusable closure (see Varargs and Closures). Tables are introduced in Tables as Arrays and Dictionaries.

Try it: memoized Fibonacci

JS Memoization stand-in (JavaScript)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does local f = function(n) ... f(n - 1) ... end fail for recursion?

    The local variable is created after the right-hand side is evaluated. local function f creates it first, which is why that form works.
  2. 2. Which of these is a proper tail call?

    Only a bare return f(args) is a tail call. In the other forms something remains to be done after the call returns.
  3. 3. What is the benefit of a proper tail call?

    Because nothing remains to do after the call, Lua replaces the frame instead of adding one.
  4. 4. What does memoization do?

    A memo table remembers results, so each distinct input is computed only once.

Summary

  • A recursive function needs a base case and a recursive case that approaches it.
  • Use local function name so the body can see its own name; local name = function cannot recurse.
  • Deep non-tail recursion eventually raises a catchable stack overflow error.
  • return f(args), and nothing else, is a proper tail call and does not grow the stack; accumulator parameters turn many recursions into tail calls.
  • Memoize with a table when a recursion recomputes the same inputs.

Next, the structure Lua is built around: Tables as Arrays and Dictionaries.