Still have questions? Join our Discord server and get real time help.

Log in to vote

2
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.

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`

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

huh? greatneil80 2145 — 1y

0

this is a great question DeceptiveCaster 2796 — 1y

Log in to vote

3
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 `n`

s have been replaced with `3`

s:

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!

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 `return`

ed 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.

Log in to vote

1
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

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 BlueTaslem 17922 — 1y

Log in to vote

0
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

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. RayCurse 1508 — 1y

1

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) BlueTaslem 17922 — 1y

0

Actually, I agree with you there. I have definitely made a mistake there. This is _not_ tail recursive. GameAnnounce 3 — 1y

Log in to vote

-2
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

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. DeceptiveCaster 2796 — 1y

1

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