Understanding a Common Recursion Mistake in Lua: Why Calling fact(n) Instead of fact(n – 1) Causes Infinite Recursion

[Rajeev Bagra]

While learning recursive functions in Lua, a learner attempted to write a factorial function but accidentally introduced a subtle logic error.

The learner wrote something similar to:

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

At first glance, the code appears reasonable because it seems to be multiplying the current number by a smaller number. However, the recursive call contains a critical mistake.

The Problem

The recursive call is:

fact(n)

Notice that the value of n is not changing.

If the learner calls:

fact(5)

Lua attempts to evaluate:

fact(5) * 4

Before Lua can perform the multiplication, it must first determine the value of:

fact(5)

This creates another call to:

fact(5)

That new call again attempts to evaluate:

fact(5) * 4

which creates yet another call to:

fact(5)

The chain continues indefinitely:

fact(5)
   ↓
fact(5)
   ↓
fact(5)
   ↓
fact(5)
   ↓
...

The value of n never changes.

As a result, the function never reaches its stopping condition.

The Base Case Is Never Reached

The function contains a base case:

if n == 0 then
    return 1
end

The purpose of this condition is to stop the recursion.

However, because every recursive call uses the same value of n, the function never moves closer to:

n == 0

The base case remains unreachable.

The Correct Recursive Call

The recursive call should reduce the problem size:

return fact(n - 1) * n

or equivalently:

return n * fact(n - 1)

Now each recursive call decreases the value of n:

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

Eventually the base case is reached:

return 1

After that, the waiting function calls begin returning their results.

A Useful Rule for Recursive Functions

When designing a recursive function, every recursive call should move closer to the base case.

For the factorial problem, the path toward the base case is:

n
↓
n - 1
↓
n - 2
↓
...
↓
0

If the recursive call does not make progress toward the base case, the recursion will never terminate.

Key Takeaway

The learner discovered that recursion requires more than simply calling the same function again. Every recursive call must reduce the problem and move closer to a stopping condition. Calling fact(n) repeatedly with the same value of n creates infinite recursion, while calling fact(n - 1) gradually leads the function to its base case and allows the factorial calculation to complete successfully.

This is one of the most important early lessons in recursion: a recursive function must always make progress toward its base case.

[Author]

Posts