C Program To Find Factorial Of A Number Using Recursion Function

Factorial, a fundamental concept in mathematics, represents the product of all positive integers less than or equal to a given positive integer. It finds its use in various fields, from probability to algorithm analysis. In this article, you will learn how to compute the factorial of a number using a recursive function in C.

Problem Statement

Calculating the factorial of a non-negative integer n involves multiplying all positive integers from 1 up to n. Mathematically, this is denoted as n!. For instance, 5! is 5 * 4 * 3 * 2 * 1. The challenge is to implement this calculation efficiently in C, particularly using the powerful concept of recursion.

Example

Let's consider finding the factorial of 5.

5! = 5 * 4 * 3 * 2 * 1 = 120

Background & Knowledge Prerequisites

To effectively understand this solution, readers should have a basic grasp of:

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

Use Cases or Case Studies

Factorials appear in a wide range of applications:

• Combinatorics and Probability: Used to calculate the number of permutations and combinations, crucial in fields like statistics and data science.
• Algorithm Analysis: Often encountered when analyzing the time complexity of certain algorithms (e.g., algorithms involving permutations).
• Series Expansions: Used in Taylor series and Maclaurin series expansions for functions like e^x or sin(x).
• Computer Science Problems: Foundation for problems like "counting paths" or "arranging items."
• Number Theory: An essential concept within the broader study of integers and their properties.

Solution Approaches

While iteration is another way to solve this, recursion offers an elegant and often more intuitive solution for problems that can be broken down into smaller, self-similar subproblems.

Approach 1: Finding Factorial using Recursion

This approach leverages the definition of factorial, where n! = n * (n-1)! and 0! = 1. The function calls itself with a smaller input until it reaches the base case, 0!.

// 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 is 1
    if (n == 0) {
        return 1;
    }
    // Step 2: Define the recursive step
    // n! = n * (n-1)!
    else {
        return (long long)n * factorial(n - 1);
    }
}

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

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

    // Step 2: Validate input
    if (num < 0) {
        printf("Factorial is not defined for negative numbers.\\n");
    } else {
        // Step 3: Call the recursive factorial function
        result = factorial(num);
        // Step 4: 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

Stepwise Explanation:

1. factorial(int n) Function:

• This function is designed to compute n!. It takes an integer n as input and returns a long long to accommodate potentially large factorial values.

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

• The most crucial part of recursion is the base case. Without it, the function would call itself indefinitely, leading to a stack overflow.
• For factorials, the base case is 0! = 1. When n becomes 0, the function simply returns 1, stopping the recursion.

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

• If n is not 0, the function calculates n * factorial(n - 1).
• It calls itself with n - 1, effectively breaking down the problem into a smaller, identical subproblem.
• This continues until n reaches 0, at which point the base case is hit, and the results are multiplied back up the call stack.

1. main Function:

• It prompts the user to enter a non-negative integer.
• It includes basic input validation to ensure the number is not negative, as factorials are typically defined for non-negative integers.
• It then calls the factorial function with the user's input and prints the computed result. The long long specifier %lld is used for printing the result.

Conclusion

Recursion provides an elegant and concise way to solve the factorial problem in C. By defining a clear base case (0! = 1) and a recursive step (n! = n * (n-1)!), we can break down the problem into smaller, manageable parts that lead to the final solution. This method beautifully mirrors the mathematical definition of a factorial.

Summary

• Factorial (n!) is the product of all positive integers up to n.
• Recursion involves a function calling itself with a smaller input.
• A base case (e.g., 0! = 1) is essential to terminate the recursive calls.
• The recursive step (n * factorial(n - 1)) breaks the problem down.
• C's long long data type is used to handle large factorial values.
• Input validation is important to handle negative numbers, for which factorial is not conventionally defined.