Why Does the Recursive Factorial Function Work Without a Loop? (Lua Learning Q&A)

While reading the first chapter of Programming in Lua, I encountered the following recursive factorial function:

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

At first, I was confused.

I understood how a factorial should work:

5! = 5 × 4 × 3 × 2 × 1 = 120

However, I could not see any for loop or while loop in the function. There was only an if statement.

My initial thought was:

The function seems to calculate only one step, reducing n to n - 1. How does it continue all the way down to 1?

The Key Idea: The Function Calls Itself

The answer lies in the line:

return n * fact(n - 1)

The function is not simply performing a multiplication once. Instead, it is calling itself again with a smaller value.

This technique is called recursion.

In recursion, a function solves a problem by repeatedly calling itself with smaller and smaller versions of the original problem.

Tracing fact(5)

Suppose we call:

fact(5)

Since 5 is not zero, Lua executes:

5 * fact(4)

But before Lua can multiply by 5, it must first determine the value of fact(4).

So Lua pauses the current calculation and starts another function call.

That new call becomes:

4 * fact(3)

Again, Lua must determine fact(3).

This process continues:

fact(5)
= 5 × fact(4)

fact(4)
= 4 × fact(3)

fact(3)
= 3 × fact(2)

fact(2)
= 2 × fact(1)

fact(1)
= 1 × fact(0)

The Base Case Stops the Recursion

Eventually Lua reaches:

fact(0)

This time the condition is true:

if n == 0 then
    return 1
end

Therefore:

fact(0) = 1

No further recursive calls occur.

Unwinding the Call Stack

Now Lua starts returning values back through all the waiting function calls.

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

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

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

fact(4)
= 4 × fact(3)
= 4 × 6
= 24

fact(5)
= 5 × fact(4)
= 5 × 24
= 120

Therefore:

fact(5) = 120

Visualizing the Recursive Calls

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

Once fact(0) returns 1, the answers travel back upward until the original call is completed.

Recursion vs Loops

The recursive factorial function does not contain an explicit loop.

However, the repeated self-calls behave like a loop.

The recursive version:

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

is conceptually similar to an iterative version:

function fact(n)
    local result = 1

    for i = 1, n do
        result = result * i
    end

    return result
end

Both produce the same answer.

The difference is that the loop repeats explicitly, while recursion repeats through repeated function calls.

Important Lesson

Every recursive function needs two parts:

1. A recursive step that reduces the problem:

fact(n - 1)

2. A base case that stops the recursion:

if n == 0 then
    return 1
end

Without the base case, the function would continue calling itself forever until the program eventually crashed with a stack overflow error.

Conclusion

The factorial function works without a visible loop because recursion itself provides the repetition. Each call creates another smaller call until the base case is reached. After that, the results are returned back through the chain of calls until the original problem is solved.

This example demonstrates one of the most important ideas in computer science: a function can solve a complex problem by repeatedly solving smaller versions of the same problem.

:::

This is one of the first classic recursion examples you’ll encounter not only in Lua, but also in Python, C, Java, and many other programming languages.