Recursion in C

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem. It’s a powerful concept used in algorithms and programming languages like C. Here’s a detailed explanation of recursion along with an example C program:

1. Basic Idea:
   • Recursion involves breaking down a problem into smaller, similar sub-problems until a base case is reached, which can be solved directly without further recursion.
   • Each recursive call works on a smaller instance of the problem, eventually leading to the base case where the recursion stops.
2. Components of Recursion:
   • Base Case: This is the termination condition that stops the recursion. It defines the smallest instance of the problem that can be solved directly.
   • Recursive Case: This is where the function calls itself with modified arguments to solve a smaller instance of the problem.
3. Example Program – Factorial Calculation:
   • One classic example of recursion is computing the factorial of a non-negative integer n, denoted as n!. The factorial of n is the product of all positive integers less than or equal to n.
   • The recursive formula for factorial is: n! = n * (n-1)!
   • Here’s a C program to calculate factorial using recursion:

#include <stdio.h>

// Function prototype

unsigned long long factorial(int n);

int main() {

    int n;

    printf(“Enter a non-negative integer: “);

    scanf(“%d”, &n);

    // Call the factorial function and print the result

    printf(“Factorial of %d = %llu\n”, n, factorial(n));

    return 0;

}

// Recursive function to compute factorial

unsigned long long factorial(int n) {

    // Base case: Factorial of 0 is 1

    if (n == 0) {

        return 1;

    }

    // Recursive case: n! = n * (n-1)!

    else {

        return n * factorial(n – 1);

    }

}

4. Explanation:
   • In the program, the factorial() function is defined to compute the factorial of a non-negative integer n.
   • Inside the factorial() function, there are two cases:
     • Base Case: If n is 0, the function returns 1, as the factorial of 0 is defined as 1.
     • Recursive Case: Otherwise, the function returns n * factorial(n – 1), which is the recursive call to calculate the factorial of n-1.
   • The main() function prompts the user to enter a non-negative integer, calls the factorial() function with the user input, and prints the result.
5. Execution:
   • When the program runs, the factorial() function is called recursively with decreasing values of n until n becomes 0 (the base case).
   • At this point, the recursion stops, and the factorial values are computed backward, multiplying the results as the recursion unwinds.
6. Considerations:
   • Recursion can be less efficient than iteration (looping) due to the overhead of function calls and stack usage.
   • Proper termination conditions (base cases) are essential to prevent infinite recursion.
   • Recursion is well-suited for problems that can be naturally broken down into smaller sub-problems, such as tree traversal, sorting algorithms (e.g., quicksort), and certain mathematical computations.

This example illustrates the concept of recursion in C programming and demonstrates how it can be used to solve problems by breaking them down into smaller instances.