C++ Program To Find Factorial Of A Given Number Using Recursion

Finding the factorial of a number is a fundamental problem in mathematics and computer science, often used to illustrate core programming concepts. In this article, you will learn how to implement a C++ program to calculate the factorial of a given non-negative integer using a recursive approach.

Problem Statement

The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, 5! = 5 × 4 × 3 × 2 × 1. A special case is 0!, which is defined as 1. This mathematical operation is crucial in various fields, including probability, combinatorics, and algorithm analysis, making its efficient computation a valuable skill.

Example

Let's illustrate with a simple example: finding the factorial of 5. The calculation is straightforward: 5! = 5 × 4 × 3 × 2 × 1 = 120

Background & Knowledge Prerequisites

To understand this article, readers should have a basic understanding of:

• C++ Basics: Variables, data types, input/output operations.
• Functions: How to define, declare, and call functions in C++.
• Control Flow: Conditional statements (if-else).
• Recursion Concept: A function calling itself, including the idea of a base case and a recursive step.

Use Cases or Case Studies

Factorials and the underlying recursive thinking have numerous applications:

• Combinatorics: Calculating the number of permutations (arrangements) of n distinct items, which is n!.
• Probability: Determining the likelihood of certain events, often involving combinations and permutations.
• Series Expansion: Used in Taylor series and Maclaurin series for approximating functions (e.g., e^x, sin(x)).
• Dynamic Programming: Problems like the N-Queens puzzle or tree traversals often use recursive logic.
• Algorithm Analysis: Used to determine the complexity of certain sorting algorithms or data structures.

Solution Approaches

While factorials can be computed iteratively using loops, this article focuses on the elegance and conceptual clarity offered by recursion.

1. Finding Factorial Using Recursion

Recursion involves a function calling itself until it reaches a base case, which stops the recursive calls. For factorials, the base cases are 0! = 1 and 1! = 1. The recursive step involves breaking down n! into n * (n-1)!.

// Factorial using Recursion
#include <iostream>
using namespace std;

// Function to calculate factorial using recursion
long long factorial(int n) {
    // Base case: if n is 0 or 1, factorial is 1
    if (n == 0 || n == 1) {
        return 1;
    }
    // Recursive case: n * factorial(n-1)
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    // Step 1: Declare a variable to store the input number
    int number;

    // Step 2: Prompt the user to enter a non-negative integer
    cout << "Enter a non-negative integer: ";
    cin >> number;

    // Step 3: Check for invalid input (negative number)
    if (number < 0) {
        cout << "Factorial is not defined for negative numbers." << endl;
    }
    // Step 4: Calculate and display the factorial for valid input
    else {
        long long result = factorial(number);
        cout << "Factorial of " << number << " is: " << result << endl;
    }

    return 0;
}

Run

Sample Output:

Enter a non-negative integer: 5
Factorial of 5 is: 120

Stepwise Explanation:

1. Function factorial(int n): This function takes an integer n as input and returns its factorial.
2. Base Case (if (n == 0 || n == 1)): This is the stopping condition for the recursion. If n is 0 or 1, the function immediately returns 1, as 0! = 1 and 1! = 1. Without a base case, the function would call itself indefinitely, leading to a stack overflow.
3. Recursive Case (else { return n * factorial(n - 1); }): If n is greater than 1, the function multiplies n by the result of calling itself with n - 1.
   • For factorial(5): It computes 5 * factorial(4).

1. main Function:
   • It prompts the user to enter a non-negative integer.

Conclusion

Recursion provides an elegant and concise way to solve problems that can be broken down into smaller, self-similar subproblems. Calculating the factorial of a number is a classic example that effectively demonstrates the power of recursive thinking, relying on a well-defined base case and a clear recursive step. While potentially less memory-efficient than an iterative approach for this specific problem due to function call overhead, it offers significant clarity for certain types of problems.

Summary

• Factorial Definition: n! = n × (n-1) × ... × 1, with 0! = 1.
• Recursive Approach: A function calls itself to solve a smaller instance of the same problem.
• Base Case: Essential stopping condition (e.g., factorial(0) or factorial(1) returns 1) to prevent infinite recursion.
• Recursive Step: Breaks down the problem into a simpler version (e.g., n * factorial(n-1)).
• C++ Implementation: Involves defining a recursive function and handling user input and output.
• Data Type: Use long long for factorial results to accommodate rapidly growing values.