Functions That Call Themselves
A function can call other functions. It can also call itself. This is called recursion, and it is another way to repeat work, like a loop.
function countdown(n)
if n == 0 then
print("Go!")
return
end
print(n)
countdown(n - 1)
end
countdown(3)
Output:
3
2
1
Go!
Follow the calls step by step:
countdown(3)prints 3 and callscountdown(2).countdown(2)prints 2 and callscountdown(1).countdown(1)prints 1 and callscountdown(0).countdown(0)printsGo!and returns without calling itself again.
Then each call finishes in turn, from the last one back to the first.
The two parts of every recursive function
- The base case is an input the function can answer without calling itself. Here it is
n == 0. This is how the calls stop. - The recursive case does a small piece of the work and calls the function again with a smaller input, here
n - 1.
If the input never gets smaller, the calls never reach the base case. Here the - 1 is missing:
function countdown(n)
if n == 0 then
return
end
countdown(n)
end
countdown(3)
Output:
/usr/bin/lua5.4: main.lua:5: stack overflow
Each call waits for the call it started, and Lua keeps every waiting call in memory. That memory is called the stack. When too many calls pile up, the stack fills up and the program stops with a stack overflow error. Treat it like a while loop and ask two questions: where does it stop, and what moves it closer to stopping?
When to use recursion
A loop can do anything recursion can do, and for a countdown a loop is simpler. Recursion is a good fit when a problem contains smaller copies of itself. A folder holds files and other folders, and those folders hold more folders.
Factorial is the classic first example. 5! (five factorial) is 5 * 4 * 3 * 2 * 1, which is the same as 5 * 4!. The definition uses itself, so the code can too.
In the exercise, the base case of factorial is written for you. Complete the recursive case.