🎓 A1Learner
🔍
0 of 47 lessons completed

Lua Recursion

Recursion is when a function calls itself to work through a problem in smaller steps. Every recursive function needs a stopping case that ends the chain of calls.

Countdown reaches its stopping case

countdown prints its number, then calls itself with one less. At zero it prints Go instead of calling again.

local function countdown(n)
  if n == 0 then
    print("Go")
  else
    print(n)
    countdown(n - 1)
  end
end

countdown(3)

Factorial multiplies on the way back

factorial(0) returns 1 and stops the chain. Each waiting call multiplies its own number in, and factorial(5) prints 120.

local function factorial(n)
  if n == 0 then
    return 1
  end
  return n * factorial(n - 1)
end

print(factorial(5))

Adding the numbers down to zero

sumTo adds its number to the sum of all the smaller numbers. sumTo(4) works down to the stopping case at zero and prints 10.

local function sumTo(n)
  if n == 0 then
    return 0
  end
  return n + sumTo(n - 1)
end

print(sumTo(4))

Example

local function pow(base, exp)
  if exp == 0 then
    return 1
  end
  return base * pow(base, exp - 1)
end

print(pow(2, 5))

Key points

  • Self-call: a recursive function includes a call to itself inside its own body.
  • Stopping case: one condition ends the calls instead of calling the function again.
  • Progress: each new call must move closer to the stopping case.
  • Combining: as the calls finish, each one hands a value back and the partial results combine.
  • Depth: small inputs keep the chain of calls short and easy to follow.

In this example, pow multiplies the base once for each count of exp, and each call lowers exp by one. The stopping case at exp zero returns 1, the multiplications combine to 32, and the result prints as a whole number.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

Why does a recursive countdown need a stopping case such as n == 0?