Why Doesn’t a Recursive Function Stop at the First Return Statement? Understanding Recursion, Function Calls, and the Call Stack in Lua

[Rajeev Bagra]

While studying the recursive factorial function from Programming in Lua, I encountered two questions that often confuse beginners:

1. If an if statement only executes once, how does the factorial function keep reducing the number until it reaches zero?
2. If the function encounters a return statement immediately, why doesn’t the function terminate right away?

The factorial function is shown below:

function fact(n)
    if n == 0 then
        return 1
    else
        return n * fact(n - 1)
    end
end

At first glance, it appears that the function only performs one subtraction and then returns. However, recursion works differently from ordinary sequential code.

The First Misconception: The if Statement Is Not Repeating

Many beginners assume that the if statement somehow performs the repetition.

However, the if statement executes only once during each function call.

For example, if we call:

fact(5)

Lua enters the function with:

n = 5

Then it evaluates:

if n == 0 then

Since 5 is not equal to 0, Lua executes:

return 5 * fact(4)

The repetition comes from:

fact(4)

which is a new function call.

The function starts over from the beginning with a new value:

n = 4

Again, the if statement executes once.

This process continues:

fact(5)
fact(4)
fact(3)
fact(2)
fact(1)
fact(0)

Each call executes the if statement only once.

The repetition comes from the function repeatedly calling itself.

Recursion Is Different from a Loop

With a loop:

for i = 1, 5 do
    print(i)
end

One function call contains many iterations.

With recursion:

fact(5)

many function calls occur, each containing a single execution of the if statement.

This is the key distinction between iteration and recursion.

The Second Misconception: Why Doesn’t Return End Everything Immediately?

Another common question is:

If the function encounters a return statement, shouldn’t the function terminate immediately?

Consider:

return 3 * fact(2)

Many beginners mentally read this as:

1. Encounter return
2. Terminate function

However, Lua cannot return a value until it knows what the value actually is.

To return:

3 * fact(2)

Lua must first calculate:

fact(2)

An Arithmetic Analogy

Suppose we write:

print(3 * (2 + 1))

Lua cannot calculate:

3 × ?

until it first computes:

2 + 1 = 3

Only then can it compute:

3 × 3 = 9

The recursive factorial function works the same way.

Tracing fact(3)

Suppose we call:

fact(3)

Lua encounters:

return 3 * fact(2)

Before returning, it must compute fact(2).

So it creates another function call.

Call #1

fact(3)
needs fact(2)

Call #2

fact(2)
needs fact(1)

Call #3

fact(1)
needs fact(0)

Call #4

fact(0)

Now the base case is reached:

if n == 0 then
    return 1
end

This call immediately returns:

1

Unwinding the Calls

Now the waiting calls can continue.

fact(1)
= 1 × fact(0)
= 1 × 1
= 1

Therefore:

fact(1) returns 1

Next:

fact(2)
= 2 × fact(1)
= 2 × 1
= 2

Therefore:

fact(2) returns 2

Finally:

fact(3)
= 3 × fact(2)
= 3 × 2
= 6

Therefore:

fact(3) returns 6

Visualizing the Call Stack

The recursive calls build a stack:

fact(3)
 |
 +-- fact(2)
      |
      +-- fact(1)
           |
           +-- fact(0)

The base case returns first:

fact(0) = 1

Then the answers travel back upward:

fact(1) = 1
fact(2) = 2
fact(3) = 6

This stack of waiting function calls is known as the call stack.

The Most Important Insight

Recursion is not:

One function running forever

Instead, recursion is:

Many function calls,
each waiting for the next one to finish.

Every call executes its own if statement once.

Every call eventually terminates when it reaches its own return.

The apparent repetition comes from the creation of new function calls, not from repeated execution of the same if statement.

Conclusion

The factorial function works because each recursive call reduces the problem to a smaller version of itself. The if statement does not perform iteration; it merely decides whether to stop or continue. Likewise, the first return statement does not immediately end the entire computation because Lua must first evaluate the recursive function call inside the return expression.

Understanding that recursive calls create a chain of waiting function executions is one of the most important milestones in learning recursion and computer science.

:::This realization—that return n * fact(n – 1) cannot return until fact(n – 1) is known—is often the moment when recursion finally starts to make sense.

[Author]

Posts