Recursion

Recursion in C programming refers to the ability of a function to call itself during its execution. Recursive functions consist of a base case and a recursive case. The base case is the condition that stops the recursion, while the recursive case calls the function again with a modified version of the problem.

Let’s write a C program to calculate the factorial of a number using recursion:

The factorial of a non-negative integer n is denoted by n! and is the product of all positive integers less than or equal to n. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120.

For instance

#include <stdio.h> 

// Recursive function to calculate factorial
int factorial(int n) {
    // Base case: factorial of 0 is 1
    if (n == 0)
        return 1;
    
    // Recursive case: factorial of n is n * factorial(n - 1)
    return n * factorial(n - 1);
}

int main() {
    int number;
    printf("Enter a non-negative integer: ");
    scanf("%d", &number);

    if (number < 0) {
        printf("Factorial is not defined for negative numbers.\n");
    } else {
        int result = factorial(number);
        printf("Factorial of %d is %d.\n", number, result);
    }

    return 0;
}

Output

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

In this program, the factorial function is defined to calculate the factorial of a given non-negative integer n. It uses recursion to break down the problem into smaller instances until it reaches the base case (factorial of 0), where it returns 1.

When you run this program and enter a non-negative integer, it will calculate and display the factorial of that number. Keep in mind that recursion may not be the most efficient solution for all problems, and in some cases, it may lead to stack overflow errors for very large inputs. However, it’s a powerful technique for certain types of problems where it provides a clear and concise solution.

Here’s how it works:

1. Factorial Definition: 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 = 120.
   
   
2. Recursive Function: In the C program, we have defined a function named factorial that takes an integer n as input and returns the factorial of n as output.
   
   
3. Base Case: Recursion requires a base case to stop the recursive calls. In this example, the base case is when n equals 0. In this case, the function returns 1, as it defines the factorial of 0 to be 1.
   
   
4. Recursive Case: If the input n is greater than 0 (not a base case), the function calculates the factorial using recursion. It multiplies n with the result of factorial(n – 1), which will calculate the factorial of the number one less than n. This process continues until reaching the base case.
   
   
5. User Input and Output: The main function takes a non-negative integer as input from the user. If the number is negative, it displays a message indicating that the factorial is not defined for negative numbers. Otherwise, it calls the factorial function to calculate the factorial of the given number and displays the result.
   
   
6. Recursion Flow: When the factorial function is called, it keeps calling itself with smaller values until it reaches the base case (when n becomes 0). Then, it starts unwinding the recursive calls and calculates the final result step-by-step.

For example, if the user enters 5, the steps of recursion would be:

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * (1 * factorial(0)))))
= 5 * (4 * (3 * (2 * (1 * 1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

The program calculates the factorial of 5 as 120 and displays the output as “Factorial of 5 is 120.“

Advantages of Recursion in C:

• Elegance and simplicity in code.
• Divide and conquer approach for complex tasks.
• Reduced code complexity.
• Flexibility and adaptability to different problem variations.
• Natural fit for certain problems.

Disadvantages of Recursion:

• Risk of stack overflow.
• Increased memory overhead.
• Potential performance issues.
• Difficulty in debugging.
• Not all compilers support tail call optimization.
• Not always the most efficient solution for all problems.