Introduction to Recursion

Recursion is a programming technique in which a function calls itself directly or indirectly to solve a problem. Each recursive call reduces the problem into smaller instances, and the function continues calling itself until it reaches a base case, which is the simplest instance of the problem. Recursion is commonly used for tasks like searching, sorting, and calculating mathematical sequences.

How Recursion Works

In a recursive function, each call to itself is executed with different parameter values. The key components of recursion are:

• Base Case: A condition that stops the recursion. Without a base case, the function would call itself indefinitely, leading to a stack overflow.
• Recursive Case: The function performs part of the task and then calls itself with modified parameters, working toward the base case.

Understanding recursion is essential as it allows for elegant solutions to complex problems by breaking them down into simpler, manageable parts.

Example: Factorial Calculation Using Recursion

In this example, we use recursion to calculate the factorial of a number. The factorial of a positive integer n is defined as n! and calculated as:
n! = n * (n - 1) * (n - 2) * ... * 1
In a recursive approach, we define the factorial function such that factorial(n) = n * factorial(n - 1), with the base case being factorial(1) = 1.

#include <stdio.h>
// Recursive function to calculate factorial
int factorial(int n) {
    if (n == 1) {       // Base case
        return 1;
    }
    return n * factorial(n - 1);   // Recursive call
}
// Main Function
int main() {
    int num = 5;
    printf("Factorial of %d is: %d\n", num, factorial(num));
    return 0;
}

Additional Example: Fibonacci Sequence Using Recursion

Another common example of recursion is calculating the Fibonacci sequence. The Fibonacci sequence is defined as:
F(n) = F(n - 1) + F(n - 2), with the initial conditions F(0) = 0 and F(1) = 1.
Using recursion, we can compute the nth term in the sequence.

#include <stdio.h>
// Recursive function to calculate Fibonacci number
int fibonacci(int n) {
    if (n == 0) {       // Base case
        return 0;
    }
    if (n == 1) {       // Base case
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);   // Recursive call
}
// Main Function
int main() {
    int num = 6;
    printf("Fibonacci number at position %d is: %d\n", num, fibonacci(num));
    return 0;
}

Advantages and Disadvantages of Recursion

• Can simplify code by breaking down complex problems into smaller, manageable sub-problems.
• Effective for solving problems with a natural recursive structure, like mathematical sequences.

• Can be memory-intensive and slower than iterative solutions due to repeated function calls.
• May lead to stack overflow if the base case is not reached.