Recursion
Recursion is a technique used to use an algorithm or function that calls itself repetitively until a certain condition is satisfied.
The go-to example for recursion is a factorial function:
1
function fact(n)
2
if n == 0 then
3
return 1
4
end
5
return n * fact(n - 1)
6
end
Copied!
Here it will calculate the factorial by returning each value multiplied by the result of `fact(n - 1)`. It can be a bit confusing, since we know return breaks out and gives back a value to whatever called the function, but before a return can give back a value, it needs to be evaluated first. And until `n` reaches 0, it will keep trying to evaluate `n * fact(n - 1)` . Once `n` does reach 0, it returns the next multiplier (1) and then the first call to `fact` will be able to return the evaluated result. All of these is quite literally a chain of returns.
Here's a diagram of what's really happening:
1
fact(3)
2
--[[
3
fact(3)
4
|
5
-> return (3 * fact(2))
6
|  (3 * 2) |
7
| | -> return (2 * fact(1))
8
| <-------  (2 * 1) |
9
| | -> return (1 * fact(0))
10
| | |
11
| | -> return 1
12
| <----------  (1 * 1)
13
-> fact(3) = 6, (3 * 2) end result
14
]]
Copied!
Here you can see the chain of returns, and how each `fact` call looks. Each time there's an attempt to return, it must evaluate what the value of `fact(n - 1)` is before giving back a value. Which is why the second it tries to return `3 * fact(2)`, it evaluates `fact(2)`, but `fact(2)` will have to evaluate `fact(1)`, and `fact(1)` will have to evaluate `fact(0)`. The second that chain breaks by returning 1, it goes back up each return and will "insert" the result of that `fact` call and multiply it. I tried to show this as best I could, the return statements evaluated in parentheses, the result in square brackets [X] and a display to show the chain of where it's inserted/used as the multiplier in the above return.
Another example of recursion would be a Fibonacci sequence:
1
function fib(n)
2
if n < 3 then
3
return 1
4
end
5
return fib(n-1) + fib(n-2)
6
end
Copied!
Here, it will calculate n-1 + n-2 until both `n`s reach a value which is less than 3. Each of these `fib` calls chain out like `fact` did, each call must be evaluated before it can be returned for usage.
1
fib(5)
2
--[[
3
fib(5) | Result: 5
4
| ^
5
| |
6
| ----------------------|
7
--> return fib(4) + fib(3) | (3+2) 
8
| ^ ^ |
9
| | | ---> return fib(2) + fib(1) | (1+1) 
10
| | --------------------------------------------|
11
| |
12
| -------------------------------------|
13
---> return fib(3) + fib(2) | (2+1) 
14
^ | ^ |
15
| | | -> return 1 
16
| | -----------------|
17
| |
18
| -> return fib(2) + fib(1) | (1+1) 
19
| ^ | ^ | |
20
| | | | -> return 1  |
21
| | | ---------------| |
22
| | -> return 1  |
23
| ---------------| |
24
------------------------------------------|
25
]]
Copied!
Again, the evaluation is in parentheses, the result is in square brackets and moves back up the chain. Reading this diagram, you go bottom-right, then follow the square brackets back up the chain, up-left.