Site icon Gloritech

Simple Recursive Factorial Function Using a Native Type in C/C++

admin

 #include<iostream>

// Simple recursive factorial using a native type (unsigned long long).
// Note: overflow for n > 20 on 64-bit unsigned long long.
unsigned long long fact_recursive(unsigned n) {
return (n <= 1) ? 1ULL : n * fact_recursive(n – 1);
}

int main() {
unsigned n;
std::cout << “Enter a non-negative integer: “; if (!(std::cin >> n)) return 1;

if (n > 20) {
std::cout << “Warning: result will overflow unsigned long long for n > 20.” << std::endl;
}

unsigned long long result = fact_recursive(n);
std::cout << n << “! = ” << result << std::endl;
return 0;
}

Simple Recursive Factorial Using a Native Type

Simple Recursive Factorial Using a Native Type

Introduction

The factorial function is a fundamental concept in mathematics and computer science. It appears in combinatorics, probability, statistics, and algorithm design. In simple terms, the factorial of a number n is the product of all positive integers less than or equal to n. For example, 6! = 6 x 5 × 4 × 3 × 2 × 1 = 720.

Recursive Definition

Mathematically, factorial is defined as:

n! = n × (n-1)! with 0! = 1

This definition is naturally recursive: to compute n!, you need to compute (n-1)!.

Recursive Implementation in C++


#include <iostream>
using namespace std;

long long factorial_recursive(int n) {
    if (n == 0) return 1;   // Base case
    return n * factorial_recursive(n - 1);
}

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;

    cout << "Recursive factorial of " << num << " = "
         << factorial_recursive(num) << endl;

    return 0;
}

Recursive Implementation in C


#include <stdio.h>


    long long factorial_recursive(int n) {
        if (n == 0) return 1;   // Base case
        return n * factorial_recursive(n - 1);
    }
    
    int main() {
        int num;
        cout << "Enter a number: ";
        cin >> num;
    
        cout << "Recursive factorial of " << num << " = "
         << factorial_recursive(num) << endl;

    return 0;
}

Iterative vs Recursive


long long factorial_iterative(int n) {
    long long result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}
  • Recursive: Elegant and close to the mathematical definition.
  • Iterative: Often more efficient and avoids stack overflow issues.

Limitations

Factorials grow extremely fast. For example, 20! ≈ 2.43 × 1018. This exceeds the range of a standard int.

  • Use long long for larger values.
  • Use unsigned long long for values up to about 20! safely.
  • For very large factorials, C/C++ requires external libraries such as GMP or Boost.Multiprecision.

Practical Applications

  • 🎲 Permutations: number of ways to arrange elements.
  • 📊 Combinations: calculating probabilities.
  • 💻 Algorithms: complexity analysis and mathematical structures.

Conclusion

Recursion provides an elegant way to implement factorial, but it comes with limitations in performance and memory. For real-world applications, iterative solutions or specialized libraries are often preferred.

Exit mobile version