C - Recursion

Recursion in C is a programming technique where a function calls itself repeatedly until a specific condition is met. It allows solving complex problems by breaking them down into smaller, simpler instances of the same problem. Recursion consists of two components: base case and recursive case. Here's an explanation of recursion in C:

Base Case:

The base case is the condition that determines when the recursive function should stop calling itself and return a result. It serves as the terminating condition for the recursion. When the base case is met, the function stops calling itself and returns a value.

Recursive Case:

The recursive case is the part of the function where the function calls itself with a modified set of parameters. It represents the problem being broken down into smaller instances of the same problem. By making the problem smaller, the function moves closer to the base case.

Example: Factorial Calculation

Let's take the factorial calculation as an example to demonstrate recursion in C. The factorial of a non-negative integer n is denoted by n! and is calculated by multiplying all positive integers from 1 to n. The factorial of 0 is defined as 1.

#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: call the function with n-1
    else {
        return n * factorial(n - 1);
    }
}
int main() {
    int number = 5;
    int result = factorial(number);
    printf("Factorial of %d is %d\n", number, result);
    return 0;
}

In this example, the factorial() function is a recursive function that calculates the factorial of a given number n. In the base case, when n is 0, the function returns 1. In the recursive case, the function calls itself with n-1 and multiplies the current value of n with the result of the recursive call. This process continues until the base case is reached.

When factorial(5) is called in main(), the function calls itself with n-1 (i.e., factorial(4)), then factorial(3), factorial(2), factorial(1), and finally factorial(0). At this point, the base case is met, and the function starts returning the results back up the call stack, calculating the factorial along the way.