✓ ANSWER ACCEPTED

How EXACTLY does this recursive factorial function example work in Lua?

Asked May 28, 20191,123 views4 answers

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.

AnonymousMay 28, 2019Edited May 28, 2019

2 comments

huh?

AnonymousMay 28, 2019#

this is a great question

AnonymousMay 28, 2019#

4 answers

✓ Accepted answer

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.

AnonymousMay 29, 2019Permalink

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.

AnonymousMay 29, 2019Edited May 29, 2019Permalink

1 comment

Pedantically, I wouldn't call that the definition of n!. That's a recurrence relation, which defines a sequence rather than a function. (Formally, a sequence is a function, but is rarely treated that way; and not all recurrence relations have well-defined sequences-that-are-functions). The "formal" definition would normally be the surprisingly informal looking n! = 1 * ... * n

AnonymousMay 29, 2019#

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.

AnonymousMay 29, 2019Permalink

3 comments

That is not a tail call because it's not the last operation; the multiplication is. Nonetheless, you gave some great insight into them and the way Roblox implements them.

AnonymousMay 29, 2019#

This is not a tail call, and "when the last instruction of a function is call, that is a tail call" doesn't actually explain how recursion works (you can have non-recursive tail calls, and you can have [as this question demonstraints] non tail-call recursive calls)

AnonymousMay 29, 2019#

Actually, I agree with you there. I have definitely made a mistake there. This is not tail recursive.

AnonymousMay 29, 2019#

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. :) )

AnonymousMay 28, 2019Permalink

2 comments

He uses semicolons only because he codes in C++, a language that requires the programmer to use semicolons. Semicolons don't really have a purpose in Lua, and following C++ protocol with semicolons in Lua has no effect on how the code runs.

AnonymousMay 28, 2019#

Also, this script DOES NOT work perfectly. You'll get an error at line 5 about attempting to perform arithmetic on a function value.

AnonymousMay 28, 2019#

This discussion is preserved as it was. New answers, comments, and votes are closed.