EXAMTOPICS / TECHNOLOGY INSIGHTS

Factorial in C: Loop, Recursion and Overflow Checks

What is a factorial in C?

The factorial of a nonnegative integer n, written n!, multiplies all positive integers from 1 through n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120. The special cases 0! = 1 and 1! = 1 are important both mathematically and when designing a loop or recursive base case.

In C, the arithmetic is straightforward but the data type is a major part of correctness. Standard integer types have finite ranges. A program that multiplies without checking can overflow even though every individual input looks valid. A good factorial example therefore validates the input, detects overflow before multiplication and reports a clear result.

A checked iterative factorial program

The following C11 program uses unsigned long long, checks each multiplication against ULLONG_MAX, and returns a success flag. It stores the result through an output pointer only when computation succeeds. That avoids using a numeric value such as zero to mean an error when zero is never a valid factorial result.

#include <stdio.h>
#include <limits.h>

int factorial_checked(int n, unsigned long long *out) {
    if (n < 0 || out == NULL)
        return 0;

    unsigned long long value = 1;
    for (int i = 2; i <= n; ++i) {
        if (value > ULLONG_MAX / (unsigned)i)
            return 0;
        value *= (unsigned)i;
    }

    *out = value;
    return 1;
}

int main(void) {
    int n;
    if (scanf("%d", &n) != 1 || n < 0) {
        fputs("Enter a nonnegative integer.\n", stderr);
        return 1;
    }

    unsigned long long result;
    if (!factorial_checked(n, &result)) {
        fputs("Factorial exceeds the integer range.\n", stderr);
        return 1;
    }

    printf("%d! = %llu\n", n, result);
    return 0;
}

Build this source with a C11 compiler, for example cc -std=c11 -Wall -Wextra -pedantic factorial.c -o factorial. Test zero, one and a small positive number before trying boundary values. The code’s input handling illustrates basic validation. A production command-line utility should use a carefully checked parser such as strtol, including range and trailing-character checks, for hostile or oversized numeric text.

How the loop works

The accumulator begins at 1 because 1 is the multiplicative identity. The loop runs from 2 to n, multiplying the current accumulator by each new value. For input 5, the intermediate results are 2, 6, 24 and 120. For input 0 or 1, the loop is skipped and the initialized result of 1 is returned. This design avoids special-case code in the loop itself.

Before multiplying, the expression value > ULLONG_MAX / i asks whether multiplying value by i would exceed the maximum value representable by unsigned long long. Checking after multiplication is too late: unsigned overflow wraps modulo its range, so the result may already have become incorrect. Signed integer overflow is even more dangerous because its behavior is undefined by C.

The example uses an int argument to make a negative-input check easy to teach. It returns immediately on overflow, long before a loop over enormous ordinary inputs could wrap the loop counter on typical systems. For general-purpose libraries with a different argument contract, choose types and bounds according to the stated maximum input.

Why 20! is a useful boundary test

On a platform where unsigned long long is 64 bits, its maximum value is 18,446,744,073,709,551,615. In that environment, 20! is 2,432,902,008,176,640,000 and fits, while 21! is larger than the type’s maximum and must be rejected. C guarantees unsigned long long is at least 64 bits, but implementations can provide a wider type, so a portable program should consult ULLONG_MAX instead of assuming that 20 is the last supported input everywhere.

The C numeric limits reference summarizes the relevant macros from <limits.h>. The important lesson is not to memorize a particular machine limit, but to validate against the limit of the actual type and implementation being used.

Recursion: the same mathematical rule with different risks

Factorial also follows n! = n × (n-1)! when n ≥ 2. A simple recursive version illustrates the recurrence clearly. The following teaching function is intentionally limited to small, trusted inputs because it performs no overflow checking and each call consumes stack space.

unsigned long long factorial_small(unsigned n) {
    if (n <= 1)
        return 1ULL;
    return (unsigned long long)n * factorial_small(n - 1);
}

With factorial_small(5), the function calls itself with arguments 5, 4, 3, 2 and 1, then multiplies values while returning. The recursive form uses additional call stack for every level; C does not guarantee that a compiler will eliminate this recursion. It is not safer or necessarily faster than iteration, and passing a huge number can exhaust the stack before overflow is detected.

For externally supplied values, the checked iterative implementation is the better starting point. A checked recursive version would need to validate the result at each multiplication and enforce a safe recursion depth, adding complexity without providing an advantage for ordinary factorial calculations.

Common mistakes in C factorial programs

Initializing the accumulator to zero causes every answer to be zero. Treating a negative number as if the loop simply ran zero times produces the false result 1. Forgetting the zero case breaks a standard factorial identity. Using int to store a large factorial causes overflow much earlier than an unsigned 64-bit result. Using a floating-point value merely to delay overflow sacrifices exact integer results.

Another common mistake is printing a value with the wrong format specifier. For unsigned long long, the example uses %llu; using %d would not match the argument type and can produce undefined behavior. Compiler warnings help catch format mistakes, but cannot prove that arithmetic is correct for every input.

Input parsing needs care too. scanf is convenient for a beginner, but robust software must reject malformed and out-of-range numbers explicitly. It should not accept a partially parsed prefix and silently ignore unexplained extra characters. Document whether a function accepts only decimal text, signed text or numbers from another API.

Test cases and expected outcomes

Input Expected result on a 64-bit unsigned-long-long system
0 1
1 1
5 120
10 3,628,800
20 2,432,902,008,176,640,000
21 Reported overflow
-1 Reported invalid input

These examples test normal results, the lower boundary, a high but representable value and values that must be rejected. The C program shown above was checked with a C11 compiler using these representative cases. Broader production testing should also cover text parsing, platform-specific integer widths and the calling contract of any exported function.

Performance and memory considerations

The iterative method performs a number of multiplications proportional to n until the representable limit is reached. It uses constant additional storage beyond the result and loop variables. Recursion performs similar multiplication work but uses stack frames proportional to the argument. For fixed-width integer arithmetic, checking overflow is usually more important than tuning a tiny loop.

If an application needs larger exact factorials, choose an appropriate arbitrary-precision integer library and consider its allocation and computational cost. Do not keep widening a built-in C integer and assume it will eventually handle all inputs. Other applications need only a factorial modulo a number or a ratio of factorials; specialized algorithms can calculate those more efficiently without representing an enormous intermediate result.

Where factorial calculations are used

Factorials count arrangements of distinct objects and appear in combinations, probability distributions and series expansions. The number of permutations of n distinct objects is n!, while the number of combinations of k objects chosen from n is n! / (k! × (n-k)!). In real software, evaluate whether the final result fits the selected type before constructing multiple intermediate factorials.

For a beginner, factorial is primarily an exercise in loops, functions, validation and algorithm termination. The reliable solution is the one that matches its declared input range and reports errors instead of producing wrapped numbers. Write the simple loop, check each multiplication, test the boundaries and only then consider alternative implementations.