3.3) Recursion in C++

Recursion is a programming technique in which a function calls itself to solve a problem. It is a powerful concept that can be used to solve complex problems by breaking them down into smaller, more manageable subproblems. Recursion involves a base case that defines the termination condition, and a recursive case that breaks down the problem into simpler instances.

Here’s a detailed explanation of recursion with code examples:

1. Factorial Calculation

One of the classic examples of recursion is calculating the factorial of a number. The factorial of a non-negative integer n (denoted as n!) is the product of all positive integers less than or equal to n.

#include <iostream>

// Recursive function to calculate factorial
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // Base case: factorial of 0 and 1 is 1
    } else {
        return n * factorial(n - 1); // Recursive case
    }
}

int main() {
    int n = 5;
    int result = factorial(n);

    std::cout << "Factorial of " << n << " is: " << result << std::endl;

    return 0;
}

Output:

Factorial of 5 is: 120

2. Fibonacci Series

The Fibonacci sequence is another common example of recursion. Each number in the sequence is the sum of the two preceding ones.

#include <iostream>

// Recursive function to calculate the nth Fibonacci number
int fibonacci(int n) {
    if (n <= 1) {
        return n; // Base case: Fibonacci of 0 is 0, Fibonacci of 1 is 1
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
    }
}

int main() {
    int n = 6;
    int result = fibonacci(n);

    std::cout << "Fibonacci(" << n << ") is: " << result << std::endl;

    return 0;
}

Output:

Fibonacci(6) is: 8

3. Recursion vs. Iteration

Recursion is often compared to iteration (using loops) for solving problems. While both approaches have their own advantages, recursion can provide elegant solutions to certain problems by breaking them down into simpler cases. However, excessive recursion can lead to stack overflow errors, so it’s important to ensure that the base case is eventually reached.

4. Handling Multiple Recursive Calls

Recursion can involve multiple recursive calls, as shown in the following example that calculates the greatest common divisor (GCD) of two numbers using the Euclidean algorithm.

#include <iostream>

// Recursive function to calculate GCD using Euclidean algorithm
int gcd(int a, int b) {
    if (b == 0) {
        return a; // Base case: GCD(a, 0) is a
    } else {
        return gcd(b, a % b); // Recursive case
    }
}

int main() {
    int a = 48, b = 18;
    int result = gcd(a, b);

    std::cout << "GCD of " << a << " and " << b << " is: " << result << std::endl;

    return 0;
}

Output:

GCD of 48 and 18 is: 6

Recursion is a powerful technique that can help solve complex problems by breaking them down into smaller instances. It’s important to define a clear base case to ensure that the recursion eventually terminates. While recursion can lead to elegant and concise code, it’s also essential to be mindful of performance and potential stack overflow issues in deep recursion.