How EXACTLY does this recursive factorial function example work in Lua?
Disclaimer
I know what recursion is. I'm just having some trouble understanding a specific part of it. There are questions regarding recursion, but they are more of "what is recursion" rather than what I am asking.
Question
I will use a factorial function as an example.
The factorial is denoted by n! and a formula to get a number's factorial is
n! = n*(n - 1)*(n - 2) ...*1
A more explicit example.
5! = 5*4*3*2*1 = 120
5! = 120
Example of how to write this.
local function fact(num)
if (rawequal(num, 0)) then
return 1;
end
return num*fact(num - 1);
end
print(fact(5)); --> 120
The base case here is if (rawequal(num, 0)) then return 1; end. A base case is the "ending point" of recursion. I understand that.
What I do not understand is return num*fact(num - 1).
How does Lua know what fact(n - 1) is?
A function call can be an expression or a statement.
I know how this works, for example;
local function getAppleCount()
return 4;
end
print(3 + getAppleCount()); --> 7
It adds 3 by 4, because the return value of getAppleCount is 4. The parenthesis are important there because it will call the function, and the call evaluates to the return. Here a function call is being used an an expression.
0
0
4 answers
A functional view -- find and replace
First, I'm going to write the fact function slightly differently, because it will make the first version of my explanation easier.
function fact(n)
return n == 0
and (1)
or (n * fact(n - 1))
end
This is using and/or as a "ternary" operator. The expression cond and a or b evaluates to a when cond is true and b when cond is false. So, the above does exactly the same thing as the original program, it's just reduced to a single return statement.
Now, how does Lua evaluate fact(3)? The simplest way to think of it is just replacing fact(3) with the body of fact, where all the ns have been replaced with 3s:
fact(3) -- inline `fact`: 3 == 0 and (1) or (3 * fact(3 - 1)) -- simplify: 3 * fact(3 - 1) 3 * fact(2) -- inline `fact`: 3 * (2 == 0 and (1) or (3 * fact(3 - 1))) -- simplify: 3 * (2 * fact(4 - 1)) 3 * (2 * fact(1)) -- inline `fact`: 3 * (2 * (1 == 0 and (1) or (1 * fact(1 - 1))) -- simplify: 3 * (2 * (1 * fact(1 - 1))) 3 * (2 * (1 * fact(0))) -- inline `fact`: 3 * (2 * (1 * (0 == 0 and (1) or 0 * fact(0 - 1)))) -- simplify: 3 * (2 * (1 * 1))) 6
That is, whenever Lua comes across a call expression, it simply plugs in the numbers to the function body. A recursive function call is no different -- it just may take a while to plug in to the resulting function calls!
An imperative view -- the stack
Expressions in Lua aren't actually evaluated by replacing a function expression with the body of a function.
Before Lua is executed, it's first "compiled" into a "bytecode" -- a much tinier programming language which is smaller and faster to execute than Lua, but much harder to read and write. That byte code contains only a small number of "instructions" which do a few things.
Let's approximate Lua's bytecode with the following operations:
-- We can assign the sum, difference, or product of two variables into a third variable
v1 := (v2 + v3);
v1 := (v2 - v3);
v1 := (v2 * v3);
-- We can call a function with one variable as an argument,
-- saving the result to a second variable
v4 := f(v5);
-- We can check if two variables are equal,
-- assigning the result of the comparison to a third variable:
v6 := (v7 == v8);
-- We can do one block of code if a variable is true,
-- and otherwise another block of code:
if v9 {
codeblock_alpha
} else {
codeblock_beta
}
-- We can "return" a single variable.
return (v10);
The function fact compiled into the above "bytecode" might look something like this:
fact(n) {
is_zero := (n == 0);
if is_zero {
return 1;
} else {
smaller := (n - 1);
recursive := f(smaller);
result := (n * recursive);
return (result);
}
}
Now, how do we execute this?
First, realize an important property of local variables in Lua. Two functions that call each other that use the same local variable name still get their own variables:
function beta()
-- Define a NEW variable called `x`.
local x = 2
local b = "bye"
end
function alpha()
local x = 1
local a = "hi"
beta()
print(x) --> `1`, rather than `2` since `beta`'s `x` is a totally different variable
end
The way this works is by creating a new stack frame each time you start executing a function. All local variables live in the new stack frame, so each local x is creating an entry in different stack frames:
-- alpha() -- local x = 1 local a = "hi" -- beta() --- local x = 2 local b = "bye"
Let's return to the "bytecode" version of fact and execute it manually for fact(3). n is just a "regular" local variable, so we start like this:
==FRAME OF fact(3)== local n = 3 executing line 2
After executing line 2, we get this state:
==FRAME OF fact(3)== local n = 3 local is_zero = false executing line 3
Next we hit the if. Since the condition is_zero is false, we'll take the else branch, and the next line to execute will be line 6:
==FRAME OF fact(3)== local n = 3 local is_zero = false executing line 6
Now we execute line 6, computing n - 1:
==FRAME OF fact(3)== local n = 3 local is_zero = false local smaller = 2 executing line 7
Now we get to the interesting line, a function call. Each function call needs its own local variables, so we push a new frame onto the stack. This new frame will start executing on line 2 with n=2, since smaller is 2 in the calling frame:
==FRAME OF fact(3)== local n = 3 local is_zero = false local smaller = 2 executing line 7 ==FRAME OF fact(2)== local n = 2 executing 2
Now we do a similar thing. We compute is_zero in the new frame (leaving the old frame alone):
==FRAME OF fact(3)== local n = 3 local is_zero = false local smaller = 2 executing line 7 ==FRAME OF fact(2)== local n = 2 local is_zero = false executing 3
We take the else branch again
==FRAME OF fact(3)== local n = 3 local is_zero = false local smaller = 2 executing line 7 ==FRAME OF fact(2)== local n = 2 local is_zero = false executing 6
We compute smaller again:
==FRAME OF fact(3)== local n = 3 local is_zero = false local smaller = 2 executing line 7 ==FRAME OF fact(2)== local n = 2 local is_zero = false local smaller = 1 executing 7
and we reach another function call. This once again pushes a new stack frame:
==FRAME OF fact(3)== ...... ==FRAME OF fact(2)== local n = 2 local is_zero = false local smaller = 1 executing 7 ==FRAME OF fact(1)== local n = 1 executing 2
once again!
==FRAME OF fact(3)== ...... ==FRAME OF fact(2)== local n = 2 local is_zero = false local smaller = 1 executing 7 ==FRAME OF fact(1)== local n = 1 local is_zero = false executing 3
==FRAME OF fact(3)== ...... ==FRAME OF fact(2)== local n = 2 local is_zero = false local smaller = 1 executing 7 ==FRAME OF fact(1)== local n = 1 local is_zero = false executing 6
==FRAME OF fact(3)== ...... ==FRAME OF fact(2)== local n = 2 local is_zero = false local smaller = 1 executing 7 ==FRAME OF fact(1)== local n = 1 local is_zero = false local smaller = 0 executing 7
==FRAME OF fact(3)== ...... ==FRAME OF fact(2)== ...... ==FRAME OF fact(1)== local n = 1 local is_zero = false local smaller = 0 executing 7 ==FRAME OF fact(0)== local n = 0 executing 2
Now we're in the final call, fact(0). This one looks slightly different:
==FRAME OF fact(3)== local n = 3 ...... ==FRAME OF fact(2)== ...... ==FRAME OF fact(1)== local n = 1 local is_zero = false local smaller = 0 executing 7 ==FRAME OF fact(0)== local n = 0 local is_zero = true executing 3
==FRAME OF fact(3)== ...... ==FRAME OF fact(2)== ...... ==FRAME OF fact(1)== local n = 1 local is_zero = false local smaller = 0 executing 7 ==FRAME OF fact(0)== local n = 0 local is_zero = true executing 4
Now we are at a return statement. This will remove the currently running stack, and write the returned value into the appropriate value. Since the previous frame is executing a function on line 7 that returns into recursive, we'll update the previous stack by writing into recursive with the returned value 1.
==FRAME OF fact(3)== ...... ==FRAME OF fact(2)== local n = 2 local is_zero = false local smaller = 1 executing 7 ==FRAME OF fact(1)== local n = 1 local is_zero = false local smaller = 0 local recursive = 1 executing 8
Now executing 8 is just computing a product:
==FRAME OF fact(3)== ...... ==FRAME OF fact(2)== local n = 2 local is_zero = false local smaller = 1 executing 7 ==FRAME OF fact(1)== local n = 1 local is_zero = false local smaller = 0 local recursive = 1 local result = 1 executing 9
and now we return result which is valued 1 to the calling stack frame's receiving variable recursive:
==FRAME OF fact(3)== local n = 3 local is_zero = false local smaller = 2 executing line 7 ==FRAME OF fact(2)== local n = 2 local is_zero = false local smaller = 1 local recursive = 1 executing 8
and again:
==FRAME OF fact(3)== local n = 3 local is_zero = false local smaller = 2 executing line 7 ==FRAME OF fact(2)== local n = 2 local is_zero = false local smaller = 1 local recursive = 1 local result = 2 executing 9
and returning the result, value 2, to recursive of fact(3)'s stack frame:
==FRAME OF fact(3)== local n = 3 local is_zero = false local smaller = 2 local recursive = 2 executing line 8
and finally evaluating the final product:
==FRAME OF fact(3)== local n = 3 local is_zero = false local smaller = 2 local recursive = 2 local result = 6 executing line 9
returning the value result which is 6:
result 6
This is more or less "exactly" how Lua makes recursive functions work. It has a stack of frames, and each call makes a new frame on top of all of the existing ones; a recursive call puts yet another frame after, and when it returns it goes back to its work from earlier on.
Notice how the list of frames got bigger as execution went forward. You only have so much space for the stack; if your code needs too many stack frames, it will eventually just fail because Lua didn't make enough space for it to do its figuring.
It knows what fact(n-1) is because it evaluates it like any normal expression. If we think about it conceptually and ignore the details of the actual code, fact(n-1) would evaluate to n - 1 * fact((n-1) - 1) which would then evaluate to n - 1 * ((n - 1) - 1) * fact(((n - 1) - 1) - 1). Eventually, we would have subtracted 1 n number of times and eventually get fact(0) which can be explicitly evaluated to 1.
In terms of the actual code, remember that it will execute the function and add to the call stack. When it reaches the base case (n = 0), that specific function will return. This causes the function that called it to return as well leading to an unwinding of sorts until it finally reaches the uppermost call to the recursive function. It's important to not overcomplicate things here. Walk yourself through the steps it would take to evaluate fact(3) and it'll become quite easy to understand.
Yet another angle of looking at this is the mathematical definition.
0! = 1 n! = (n-1)!
Using this definition of factorial, you can convince yourself and maybe even prove that your function is correct and returns the correct output for any non negative integer.
1
This is actually a very interesting question and one people commonly misunderstand.
The first thing to understand, which will eventually turn out to not be the case here, are tail calls.
What is a tail call?
A tail call is basically where the last instruction of a function is a call, and in your case return num*fact(num - 1); is an example of a tail call.
Answer
Normally, I would leave it there and say it's just a tail call but a few years ago Roblox actually REMOVED tail calls for some optimisation reason (i.e. Lua's OP_TAILCALL is removed and replaced with the same case as a normal OP_CALL instruction).
This means what actually happens with your example is your statement (n - 1) is evaluated, and then passed through the function again (creating a new stack). It does this until it gets a definitive return, in your case 1. After this, the return is put onto the stack (1 -> stack) which is used by the stack above (1 * num -> stack, ...) and so forth.
The reason why this is different on Roblox is, in the past, OP_TAILCALL would optimise the tailcall by using one stack (instead of allocating a new one each time we call the function). But now a new stack is added each time, and they've added a different form of optimisation for it but I'm not too sure on the details.
You can actually test this out, I believe if you have a number which is sufficiently big you should get an error which either says stack overflow or call stack exceeded.
If you need any more elaboration please ask! I feel like I waffled on a bit and didn't really the mark.
1
1
0
Simply,Lua will give an error.
Sample, We Have A Variable:
a = 2
In real-life math, a(4+2) = 12.But In Lua You Need To Use Like This: a*(4+2) To Recieve 12.
You Need To change That:
local function fact(num)
if (rawequal(num, 0)) then
return 1
end
return num*(fact*(num - 1))
end
print(fact(5)) --> 120
(You Can Use without ';' symbol. Script Will Work Perfectly. :) )
0
1