Recursion

Recursion in C++

Recursion is a programming technique where a function calls itself in order to solve a problem. The key idea is to break down a complex problem into simpler sub-problems, solving each of them recursively. A recursive function typically has two parts:

1. Base case: The condition under which the function returns without making further recursive calls. It prevents infinite recursion.
2. Recursive case: The part where the function calls itself with a simplified or reduced version of the original problem.

How Recursion Works:

When a function calls itself, the current function call is paused until the recursive call finishes. The recursive call keeps calling itself until the base case is reached, at which point the function begins returning control back to the previous calls, effectively "unwinding" the recursion.

Key Points:

1. Base Case: This is the condition that tells the function to stop calling itself and return a value. Without a base case, recursion will continue indefinitely, leading to a stack overflow.
2. Recursive Case: This defines how the problem is broken down into smaller subproblems, each of which is solved by making a recursive call.

Example 1: Factorial Calculation

One of the most common examples used to illustrate recursion is calculating the factorial of a number. The factorial of n (denoted as n!) is the product of all integers from 1 to n. The recursive formula for factorial is:

• Base case: n! = 1 for n = 0
• Recursive case: n! = n * (n-1)!

Factorial Example in C++:

#include <iostream>
using namespace std;

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

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;
    
    cout << "Factorial of " << num << " is " << factorial(num) << endl;
    
    return 0;
}

Explanation:

• The factorial function calls itself, reducing n by 1 each time until it reaches the base case (n == 0).
• Once the base case is reached, the recursion starts returning the results, multiplying the numbers together on the way back.

Example Output:

Enter a number: 5
Factorial of 5 is 120

Example 2: Fibonacci Series

The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones, starting from 0 and 1. The recursive formula is:

• Base cases: F(0) = 0, F(1) = 1
• Recursive case: F(n) = F(n-1) + F(n-2)

Fibonacci Example in C++:

#include <iostream>
using namespace std;

// Recursive function to find the nth Fibonacci number
int fibonacci(int n) {
    // Base cases
    if (n == 0) 
        return 0;
    if (n == 1)
        return 1;
    
    // Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;

    cout << "Fibonacci number at position " << num << " is " << fibonacci(num) << endl;

    return 0;
}

Explanation:

• The fibonacci function calls itself twice for each number n, calculating the Fibonacci sequence.
• It reduces n by 1 and 2 in each call, solving the subproblems recursively.

Example Output:

Enter a number: 5
Fibonacci number at position 5 is 5

Example 3: Tower of Hanoi

The Tower of Hanoi is a puzzle involving three rods and a number of disks of different sizes. The objective is to move all the disks from one rod to another, following these rules:

• Only one disk can be moved at a time.
• Each move consists of taking the top disk from one stack and placing it on top of another stack.
• No disk may be placed on top of a smaller disk.

The recursive solution for Tower of Hanoi is:

• Base case: If there is only one disk, move it directly.
• Recursive case: Move n-1 disks to an auxiliary rod, move the nth disk to the destination rod, and then move the n-1 disks to the destination rod.

Tower of Hanoi Example in C++:

#include <iostream>
using namespace std;

// Recursive function to solve the Tower of Hanoi puzzle
void towerOfHanoi(int n, char from, char to, char aux) {
    // Base case: If only one disk, move it
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }

    // Recursive case: Move n-1 disks to auxiliary rod
    towerOfHanoi(n - 1, from, aux, to);

    // Move the nth disk to the destination rod
    cout << "Move disk " << n << " from " << from << " to " << to << endl;

    // Move the n-1 disks from auxiliary rod to destination rod
    towerOfHanoi(n - 1, aux, to, from);
}

int main() {
    int num;
    cout << "Enter the number of disks: ";
    cin >> num;

    // Solve the Tower of Hanoi puzzle
    towerOfHanoi(num, 'A', 'C', 'B'); // A -> source, C -> destination, B -> auxiliary

    return 0;
}

Explanation:

• The function towerOfHanoi moves the disks according to the recursive formula.
• First, it moves n-1 disks from the source rod to the auxiliary rod, then moves the nth disk to the destination rod, and finally moves the n-1 disks from the auxiliary rod to the destination rod.

Example Output:

Enter the number of disks: 3
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Example 4: Sum of an Array

Another classic example of recursion is calculating the sum of elements in an array. The idea is to sum up the first element, then recursively sum the remaining elements.

Array Sum Example in C++:

#include <iostream>
using namespace std;

// Recursive function to calculate the sum of elements in an array
int sumArray(int arr[], int n) {
    // Base case: if the array has no elements left
    if (n <= 0) {
        return 0;
    }
    // Recursive case: add the first element to the sum of the remaining array
    return arr[n - 1] + sumArray(arr, n - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Sum of the array: " << sumArray(arr, n) << endl;
    
    return 0;
}

Explanation:

• The function sumArray adds the last element of the array to the sum of the remaining elements by calling itself with a smaller array.

Example Output:

Sum of the array: 15

Advantages of Recursion:

1. Simplifies Code: Recursive solutions are often shorter and easier to understand than their iterative counterparts for problems that have a natural recursive structure (like factorial, Fibonacci, etc.).
2. Problem Decomposition: Recursion allows you to break a large problem into smaller subproblems.

Disadvantages of Recursion:

1. Memory Usage: Recursion uses the call stack, and deep recursion can lead to stack overflow if the base case is not reached or if there are too many recursive calls.
2. Performance Overhead: Recursive functions can have more overhead than iterative solutions due to the repeated function calls and maintaining the call stack.

Conclusion

Recursion is a powerful technique in programming that simplifies the process of solving certain types of problems, especially those that involve repetitive tasks like factorial, Fibonacci, tree traversal, and divide-and-conquer algorithms. However, it should be used carefully to avoid excessive memory consumption or infinite recursion.