Recursion in C

Recursion in C is a technique where a function calls itself to solve a smaller version of the original problem. It is commonly used in scenarios where problems can be broken down into smaller, similar subproblems. Understanding recursion requires knowledge of base and recursive cases to prevent infinite loops.

Base Case and Recursive Case in Recursion

Every recursive function must have two essential components:

  1. Base Case: The condition that stops the recursion.
  2. Recursive Case: The part where the function calls itself with modified arguments.

Understanding the Base Case

The base case is the condition that ends the recursion. Without a base case, the function will continue calling itself indefinitely, leading to a stack overflow error.

Syntax of Base Case:

</>
Copy
if (termination_condition) {
    return result; // Stop recursion
}

Explanation:

  1. The if condition checks whether the stopping criteria (base case) is met.
  2. If the condition is satisfied, the function returns a value without making a recursive call.
  3. This ensures that recursion does not continue infinitely.

Understanding the Recursive Case

The recursive case defines the logic where the function calls itself with modified parameters, solving smaller subproblems until the base case is reached.

Syntax of Recursive Case:

</>
Copy
return recursive_function(modified_parameter);

Explanation:

  1. The function calls itself with a modified parameter, reducing the problem size in each step.
  2. The recursion continues until the base case is met.
  3. The results from each recursive call are returned, ultimately forming the final solution.

When to Use Recursion?

Recursion can be used:

  1. When a problem can be divided into smaller subproblems of the same type.
  2. In mathematical computations like factorial, Fibonacci series, and power calculations.
  3. In data structures like trees and graphs (e.g., tree traversals, depth-first search).
  4. For solving problems that have natural recursive definitions, such as the Tower of Hanoi.

Examples of Recursion in C

1. Factorial of a Number Using Recursion

In this example, we will compute the factorial of a number using recursion. The factorial of a number n is defined as:

n! = n × (n-1) × (n-2) × ... × 1, and 0! = 1.

main.c

</>
Copy
#include <stdio.h>

// Function to calculate factorial using recursion
int factorial(int n) {
    if (n == 0) // Base case
        return 1;
    else
        return n * factorial(n - 1); // Recursive call
}

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

Explanation:

  1. factorial() is a recursive function that calculates the factorial of a number.
  2. The base case is when n == 0, returning 1 to stop the recursion.
  3. For n > 0, the function calls itself with n-1, multiplying the result.
  4. For example, factorial(5) computes 5 * factorial(4) and continues until factorial(0).

Output:

Factorial of 5 is 120

2. Fibonacci Series Using Recursion

In this example, we will generate the Fibonacci sequence using recursion. The Fibonacci series is defined as:

F(n) = F(n-1) + F(n-2), where F(0) = 0 and F(1) = 1.

main.c

</>
Copy
#include <stdio.h>

// Function to return nth Fibonacci number using recursion
int fibonacci(int n) {
    if (n == 0) return 0; // Base case
    if (n == 1) return 1; // Base case
    return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
}

int main() {
    int n = 6;
    printf("Fibonacci number at position %d is %d", n, fibonacci(n));
    return 0;
}

Explanation:

  1. fibonacci() is a recursive function that calculates the nth Fibonacci number.
  2. The base cases are fibonacci(0) = 0 and fibonacci(1) = 1.
  3. For n > 1, the function calls itself with n-1 and n-2 and sums the results.
  4. For example, fibonacci(6) calculates fibonacci(5) + fibonacci(4) recursively.

Output:

Fibonacci number at position 6 is 8

Conclusion

In this tutorial, we learned about recursion in C and covered:

  1. What recursion is and when to use it.
  2. Base Case and Recursive Case in Recursion
  3. How recursion can be used for mathematical calculations.
  4. Examples of computing factorial and Fibonacci series using recursion.

Recursion is a powerful technique but should be used carefully to avoid excessive memory usage and stack overflow errors.