Recursion in C

Recursion is a programming technique where a function calls itself to solve a problem. In C, recursive functions are often used for tasks that can be broken down into smaller, similar subproblems. To create a recursive function, you need to define two parts: the base case(s) and the recursive case(s).

Here’s how recursion works in C:

Base Case:

• The base case is a condition that defines when the recursion should stop. It serves as the termination condition for the recursive function.
• When the base case is met, the function returns a value without making any further recursive calls.

Recursive Case:

• The recursive case is where the function calls itself with modified arguments to work on a smaller or simpler instance of the problem.
• The recursive calls continue until the base case is reached.

Here’s a classic example of a recursive function in C: calculating the factorial of a non-negative integer.

#include <stdio.h>

// Recursive function to calculate the factorial of a non-negative integer
int factorial(int n) {
    // Base case: factorial of 0 or 1 is 1
    if (n == 0 || n == 1) {
        return 1;
    }
    // Recursive case: n! = n * (n-1)!
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    int n = 5;
    int result = factorial(n);
    printf("Factorial of %d is %d\n", n, result);
    return 0;
}

In this example:

• The base case checks if n is 0 or 1 and returns 1, indicating that the factorial of 0 and 1 is 1.
• The recursive case calculates the factorial of n by calling factorial(n - 1) and multiplying it by n. This process continues until n reaches the base case.

When you run the program, it will calculate and display the factorial of n (in this case, 5), which is 120.

Recursion is a powerful technique that can be used to solve a wide range of problems, but it should be used with caution. It’s important to ensure that the base case is reachable and that the recursive calls eventually lead to the base case to avoid infinite recursion. Additionally, recursion can consume a significant amount of memory for deep recursion, so it’s not suitable for all situations.