Recursion in C Programming

Recursion is a programming technique where a function calls itself to solve a problem by breaking it into smaller subproblems. A recursive function must have:

• A **base case** that stops recursion.
• A step that brings the function closer to the base case.

For example, consider a countdown before a rocket launch. A function like `launchCountdown(seconds)` decrements the countdown until it reaches 0 (the base case), stopping the recursion.

Example

main()
{
    printf("Small Code");
    main();
}
        

The example above demonstrates recursion, but it lacks a **base case**, making it an infinite recursion. To be valid, a recursive function must include a **controlling condition**.

Types of Recursion

Based on how recursion occurs, there are two main types:

• **Tail Recursion**
• **Non-Tail Recursion**

Tail Recursion

In tail recursion, the recursive call is the last operation performed before the function returns. This allows the compiler to optimize the recursion for better performance.

Example

#include<stdio.h>
int factorial(int n) {
    return factorial1(n, 1);
}
int factorial1(int n, int A) {
    if (n == 1)
        return A;
    else
        return factorial1(n - 1, n * A);
}
int main() {
    int x, fact;
    printf("Enter the number=");
    scanf("%d", &x);
    fact = factorial(x);
    printf("%d", fact);
}
        

Non-Tail Recursion

In non-tail recursion, additional operations occur after the recursive call. The recursive result requires further processing before returning the final output.

Example

#include<stdio.h>
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // Base case
    } else {
        // Recursive call
        return n * factorial(n - 1);
    }
}
int main() {
    int result = factorial(5);
    printf("Factorial of 5 is: %d\n", result); // Factorial of 5 is: 120
}