C++ Factorial Program: Loop, Recursion and Overflow

The factorial of n is n x (n-1) x ... x 1. For example 5! = 120. It grows very fast.

Loop and recursion

#include <iostream>

unsigned long long factorial_loop(int n) {
    unsigned long long result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

unsigned long long factorial_rec(int n) {
    return n <= 1 ? 1 : n * factorial_rec(n - 1);
}

int main() {
    std::cout << factorial_loop(5) << '\n';
    std::cout << factorial_rec(10) << '\n';
    std::cout << factorial_loop(20) << '\n';      // the biggest that fits in 64 bits
    std::cout << factorial_loop(21) << '\n';      // overflow: it wraps around, no error
}

Detect the overflow

The compiler has a built in check for overflow:

#include <iostream>
#include <optional>

std::optional<unsigned long long> safe_factorial(int n) {
    unsigned long long result = 1;
    for (int i = 2; i <= n; i++) {
        if (__builtin_mul_overflow(result, static_cast<unsigned long long>(i), &result)) {
            return std::nullopt;
        }
    }
    return result;
}

int main() {
    for (int n : {5, 20, 21, 25}) {
        if (auto f = safe_factorial(n)) std::cout << n << "! = " << *f << '\n';
        else std::cout << n << "! does not fit in 64 bits\n";
    }
}

Compile time factorial

#include <iostream>

constexpr unsigned long long factorial(int n) {
    return n <= 1 ? 1 : n * factorial(n - 1);
}

int main() {
    constexpr auto f10 = factorial(10);
    static_assert(f10 == 3628800);               // checked while compiling
    std::cout << f10 << '\n';
}

For bigger numbers you need a big integer library (like Boost.Multiprecision or GMP), because C++ has no built in big integer type. Related: C++ Recursion and C++ Data Types.

• Previous Code
• Next Code

---

Tutorials
No Content Found.

Exercises & Assignments
No Content Found.

Interview Questions & Answers
No Content Found.