C Program To Find Factorial Of A Number Using Recursion Algorithm

Factorials are a fundamental mathematical concept often encountered in probability, combinatorics, and algorithm analysis. In this article, you will learn how to implement a C program to calculate the factorial of a number using the elegant and powerful recursion algorithm.

Problem Statement

The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers less than or equal to n. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120. The factorial of 0 is defined as 1 (0! = 1). Calculating factorials efficiently is crucial in many computational tasks, especially when dealing with permutations and combinations.

Example

Let's consider the factorial of 5: 5! = 5 * 4 * 3 * 2 * 1 = 120

Background & Knowledge Prerequisites

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

• C Programming Basics: Variables, data types, input/output operations.
• Functions in C: How to declare, define, and call functions.
• Recursion: The concept of a function calling itself, including base cases and recursive steps.

Use Cases or Case Studies

Factorials and the recursive thinking behind them are applicable in various scenarios:

• Combinatorics and Probability: Calculating the number of ways to arrange items (permutations) or select items (combinations).
• Mathematical Series: Used in Taylor series expansions and other mathematical formulas.
• Algorithm Design: Recursive algorithms are common for problems like tree traversals, quicksort, and depth-first search.
• Dynamic Programming: Many dynamic programming problems can be initially formulated recursively.
• Game Development: Pathfinding algorithms and decision trees can sometimes utilize recursive logic.

Solution Approaches

While factorials can be calculated iteratively (using a loop), the prompt specifically requests a recursive approach.

Recursive Approach

Recursion involves a function calling itself until a base condition is met. For factorials, the base case is 0! = 1 and 1! = 1, and the recursive step is n! = n * (n-1)!.

// Factorial using Recursion
#include <stdio.h>

// Function to calculate factorial using recursion
long long factorial(int n) {
    // Step 1: Define the base case
    // Factorial of 0 or 1 is 1
    if (n == 0 || n == 1) {
        return 1;
    }
    // Step 2: Define the recursive step
    // n! = n * (n-1)!
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    int num;
    long long result;

    // Step 3: Prompt user for input
    printf("Enter a non-negative integer: ");
    scanf("%d", &num);

    // Step 4: Validate input
    if (num < 0) {
        printf("Factorial is not defined for negative numbers.\\n");
    } else {
        // Step 5: Call the recursive function
        result = factorial(num);
        // Step 6: Display the result
        printf("Factorial of %d = %lld\\n", num, result);
    }

    return 0;
}

Run

Sample Output

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

Enter a non-negative integer: 0
Factorial of 0 = 1

Enter a non-negative integer: -3
Factorial is not defined for negative numbers.

Stepwise Explanation

1. factorial(int n) Function:

• This function takes an integer n as input and returns its factorial.
• We use long long for the return type to handle larger factorial values, as factorials grow very quickly.

1. Base Case (if (n == 0 || n == 1)):

• This is the termination condition for the recursion. If n is 0 or 1, the function directly returns 1, preventing infinite recursion.

1. Recursive Step (else { return n * factorial(n - 1); }):

• If n is greater than 1, the function calls itself with n - 1 and multiplies the result by n.
• For example, factorial(5) calls factorial(4), which calls factorial(3), and so on, until factorial(1) returns 1. Then the results are multiplied back up the call stack: 1 * 2 * 3 * 4 * 5 = 120.

1. main Function:

• It prompts the user to enter a non-negative integer.
• It includes a basic input validation to ensure the number is not negative, as factorials are not defined for negative numbers.
• It then calls the factorial function with the user's input and prints the computed result.

Conclusion

The recursive approach provides an elegant and concise solution for calculating the factorial of a number, directly reflecting its mathematical definition. While it might involve more overhead due to function calls compared to an iterative solution, its clarity and direct mapping to the problem's definition make it a valuable method for understanding recursive programming paradigms.

Summary

• Factorial (n!) is the product of all positive integers up to n, with 0! = 1.
• Recursion involves a function calling itself.
• A base case (e.g., n=0 or n=1 returns 1) is essential to terminate recursion.
• A recursive step (e.g., n * factorial(n-1)) breaks the problem into smaller, similar sub-problems.
• The C program demonstrates how to implement this using a function that calls itself, handling input and displaying the result.