Everything About Recursion in C++ [5]

Introduction to Recursion

What is Recursion?

Recursion is a programming technique where a function calls itself to solve smaller instances of a problem until it reaches a base case. It is particularly useful for solving problems that can be broken down into simpler, self-similar problems.

Description

Recursion leverages the divide-and-conquer approach to solve complex problems by breaking them into manageable sub-problems. Each recursive call works on a smaller part of the original problem, eventually combining the results to produce the solution. Common use cases include tree traversals, combinatorial problems, and mathematical sequences like Fibonacci and factorial.

When is Recursion Useful?

Recursion is useful for problems that:

• Can be represented in terms of smaller instances of the same problem.
• Have a clear base case that terminates the recursion. Examples include finding the factorial of a number, solving the Tower of Hanoi, and computing Fibonacci numbers.

Iterative Approach vs Recursive Approach

Let's compare iterative and recursive approaches using the factorial of a number as an example.

Factorial (Iterative Approach):

int factorialIterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

Factorial (Recursive Approach):

int factorialRecursive(int n) {
    if (n == 0) return 1; // Base case
    return n * factorialRecursive(n - 1); // Recursive case
}

Suppose we want to find the factorial of 5. The iterative approach uses a loop to multiply numbers from 1 to 5, while the recursive approach breaks down the problem into smaller sub-problems until it reaches the base case as shown below:

Comparison:

Cases in Recursion

1. Base Case The condition where recursion stops. For example, in the factorial calculation, the base case is n == 0.

2. Recursive Case The part of the function where the problem is divided into smaller sub-problems. In factorial, this is n * factorial(n - 1).

Characteristics of Recursion

1. Base Case: Every recursion must have at least one base case to avoid infinite loops.
2. Progression: Each recursive call must move closer to the base case.
3. Call Stack: Recursive calls use the program's call stack, which may lead to stack overflow if not managed correctly.

Difference Between Recursion and Iteration

Example of Iteration:

for (int i = 0; i < 10; i++) {
    // Iterative logic here
}

Example of Recursion:

void recursiveFunction(int n) {
    if (n == 0) return; // Base case
    recursiveFunction(n - 1); // Recursive call
}

Visual Representation of Recursion Stack

Types of Recursion

Recursion can be broadly categorized based on the way the function calls itself and the position of the recursive call. Let's explore two key classifications:

Direct and Indirect Recursion

Direct Recursion

In direct recursion, a function directly calls itself.

Example: Calculating the factorial of a number.

int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1); // Recursive case
}

Indirect Recursion

In indirect recursion, a function calls another function, which in turn calls the first function. Example: Two functions alternately decrement a value until a base condition is met.

void functionA(int n);
void functionB(int n);
 
void functionA(int n) {
    if (n <= 0) return; // Base case
    functionB(n - 1);   // Calls another function
}
 
void functionB(int n) {
    if (n <= 0) return; // Base case
    functionA(n - 2);   // Calls back the first function
}

Tail and Non-Tail Recursion

Tail Recursion

In tail recursion, the recursive call is the last operation performed by the function. There are no pending operations after the recursive call, making it easier for the compiler to optimize using tail-call optimization. Example:

int tailFactorial(int n, int accumulator = 1) {
    if (n == 0) return accumulator; // Base case
    return tailFactorial(n - 1, n * accumulator); // Recursive call at the end
}

Advantages:

• Space-efficient due to tail-call optimization.
• Reduces the size of the recursion stack.

Non-Tail Recursion

In non-tail recursion, the recursive call is followed by additional operations. These pending operations prevent tail-call optimization. Example:

int nonTailFactorial(int n) {
    if (n == 0) return 1; // Base case
    return n * nonTailFactorial(n - 1); // Recursive call not at the end
}

Disadvantages:

• Requires more stack memory as operations are pending after the recursive call.

Key Differences Between Tail and Non-Tail Recursion

Fibonacci Series Using Recursion

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting with 0 and 1.

Description

• The Fibonacci series starts with F(0) = 0 and F(1) = 1.
• Each subsequent number is computed as F(n) = F(n-1) + F(n-2).
• Using recursion, we can break the problem into smaller sub-problems until we reach the base cases (F(0) and F(1)).

Steps to Compute Fibonacci Using Recursion

1. Define the base cases:

   • If n == 0, return 0.
   • If n == 1, return 1.

2. For other cases (n > 1):

   • Recursively compute F(n-1) and F(n-2).
   • Add their results to get F(n).

3. Combine the results to form the Fibonacci series.

Pseudocode

function fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

Implementation in C++

#include <iostream>
using namespace std;
 
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 call
}
 
int main() {
    int n;
    cout << "Enter the number of terms: ";
    cin >> n;
 
    cout << "Fibonacci series: ";
    for (int i = 0; i < n; i++) {
        cout << fibonacci(i) << " ";
    }
    return 0;
}

Recursion Tree for Fibonacci (F(4))

To compute F(4), the recursion tree would look like this:

.           F(4)
           /    \\
        F(3)    F(2)
       /   \\    /   \\
    F(2)  F(1) F(1) F(0)
   /   \\
F(1)  F(0)

Recursion Tree

A recursion tree is a visual representation of the recursive calls made by a function. It illustrates how a problem is broken down into smaller sub-problems and how the solutions are combined. Each node in the tree represents a function call, while its child nodes represent the sub-problems it spawns.

For example, in the Fibonacci sequence, the recursion tree for F(4) shows that F(4) is calculated as F(3) + F(2), and each of these calls further breaks down into smaller Fibonacci calculations until the base cases F(1) and F(0) are reached.

While recursion trees help in understanding the flow of recursive calls, they also highlight inefficiencies like repeated calculations (e.g., F(2) is computed multiple times in the Fibonacci example). This visualization emphasizes the importance of optimization techniques like memoization to improve performance.

Tower of Hanoi

What is the Tower of Hanoi?

The Tower of Hanoi is a mathematical puzzle consisting of three rods and a number of disks of different sizes. The objective is to move all the disks from the source rod to the destination rod, following a set of rules, using the auxiliary rod as a helper.

It is a classic problem to understand recursion and its applications in solving problems with repetitive, self-similar steps.

Rules of the Game

1. Only one disk can be moved at a time.
2. A disk can only be placed on top of a larger disk or an empty rod.
3. All disks start on the source rod and must be moved to the destination rod following the above rules.

Algorithm for Tower of Hanoi

To solve the Tower of Hanoi with n disks:

1. Move the top n-1 disks from the source rod to the auxiliary rod.
2. Move the largest disk (nth disk) from the source rod to the destination rod.
3. Move the n-1 disks from the auxiliary rod to the destination rod.

Pseudocode

function towerOfHanoi(n, source, destination, auxiliary):
    if n == 1:
        print "Move disk 1 from source to destination"
        return
    towerOfHanoi(n-1, source, auxiliary, destination)
    print "Move disk", n, "from source to destination"
    towerOfHanoi(n-1, auxiliary, destination, source)

Implementation in C++

#include <iostream>
using namespace std;
 
void towerOfHanoi(int n, char source, char destination, char auxiliary) {
    if (n == 1) {
        cout << "Move disk 1 from " << source << " to " << destination << endl;
        return;
    }
    towerOfHanoi(n - 1, source, auxiliary, destination);
    cout << "Move disk " << n << " from " << source << " to " << destination << endl;
    towerOfHanoi(n - 1, auxiliary, destination, source);
}
 
int main() {
    int n;
    cout << "Enter the number of disks: ";
    cin >> n;
 
    cout << "The sequence of moves is: " << endl;
    towerOfHanoi(n, 'A', 'C', 'B'); // A: source, C: destination, B: auxiliary
    return 0;
}

Recursion Tree for Tower of Hanoi (3 Disks)

For 3 disks, the recursion tree looks like this:

Each node represents a call to solve the problem for a specific number of disks. The branches show the recursive breakdown of sub-problems.

Example Execution for 3 Disks

1. Move disk 1 from A to C.
2. Move disk 2 from A to B.
3. Move disk 1 from C to B.
4. Move disk 3 from A to C.
5. Move disk 1 from B to A.
6. Move disk 2 from B to C.
7. Move disk 1 from A to C.

Key Observations

• Number of Moves: The minimum number of moves required is 2^n - 1, where n is the number of disks.
• Space Complexity: O(n) due to the recursive stack.
• Time Complexity: O(2^n) since the number of moves grows exponentially with the number of disks.

Applications of Recursion

Recursion is widely used in solving various computer science problems, including:

1. Sorting Algorithms: Algorithms like MergeSort and QuickSort use recursion to divide and conquer sub-arrays.
2. Searching Algorithms: Binary search uses recursion to search through sorted arrays by repeatedly halving the search space.
3. Tree Traversals: Recursion is used in tree structures for operations like Inorder, Preorder, and Postorder traversal.
4. Dynamic Programming: Problems like Fibonacci and Knapsack are solved recursively, often optimized with memoization.
5. Combinatorics: Generating permutations and combinations uses recursion to explore all possible combinations.
6. Backtracking: Recursion is used in solving problems like n-Queens or Sudoku, where paths are explored and backtracked.

Conclusion

Recursion is a powerful technique that simplifies solving problems with a repetitive, self-similar structure. It is commonly used in algorithms, tree operations, and combinatorics. While it is elegant and intuitive, recursive solutions can be inefficient due to excessive function calls. Optimizations like memoization and tail recursion help improve performance. Mastering recursion is essential for solving complex problems and optimizing algorithms effectively.

Happy Coding! ✨