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:
function fact(n)
    if n == 0 then
        return 1
    end
    return n * fact(n - 1)
end
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:
fact(3)
--[[
fact(3)
|
-> return (3 * fact(2))
| [6] (3 * 2)  |
|        |     -> return (2 * fact(1))
|        <------- [2] (2 * 1) |
|                         |   -> return (1 * fact(0))
|                         |                  |
|                         |                  -> return 1
|                         <---------- [1]   (1 * 1)
-> fact(3) = 6, (3 * 2) end result                                  
]]
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:
function fib(n)
    if n < 3 then
        return 1
    end
    return fib(n-1) + fib(n-2)
end
Here, it will calculate n-1 + n-2 until both ns 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.
fib(5)
--[[
fib(5) | Result: 5
  |              ^
  |              |
  |              ----------------------|
  --> return fib(4) + fib(3)  | (3+2) [5]
                | ^     ^  |
                | |     |  --->  return fib(2) + fib(1)    | (1+1) [2]
                | |     --------------------------------------------|
                | |
                | -------------------------------------|
                ---> return fib(3) + fib(2)   | (2+1) [3]
                             ^  |      ^ |                                  
                             |  |      | -> return 1   [1]
                             |  |      -----------------|
                             |  |
                             |  -> return fib(2) + fib(1)    | (1+1)  [2]
                             |              ^ |      ^ |               |
                             |              | |      | -> return 1 [1] |
                             |              | |      ---------------|  |
                             |              | -> return 1 [1]          |
                             |              ---------------|           |
                             ------------------------------------------|
  ]] 
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.
Last modified 1yr ago