Metadata

📅 Date :: 12-06-2025
🏷️ Tags :: cpp

Notes

Detailed Notes on Recursion in C++

Introduction to Recursion

Recursion is a programming technique where a function calls itself within its own definition. It is often used to break a complex problem into smaller, repeatable steps, each of which can be solved in the same way. A function that invokes itself is referred to as a recursive function.

In essence, recursion solves a problem by solving smaller instances of the same problem, which reduces the overall complexity of the code. While recursion may lead to simpler code, it does have certain trade-offs, such as increased memory usage and slower performance in some cases.

Advantages of Recursion:

Cleaner and Simpler Code: Recursive solutions tend to be cleaner and easier to understand, especially for problems that naturally fit into a recursive structure (like tree traversal or backtracking problems).
Fewer Lines of Code: Recursion can reduce the amount of code compared to an iterative approach.
Ideal for Problems Involving Recurring Sub-problems: Recursion is especially useful in problems like sorting, searching, or working with tree structures and graphs, where the problem naturally breaks down into smaller sub-problems.

Disadvantages of Recursion:

Memory Usage: Each recursive call adds a frame to the call stack, and if too many recursive calls are made without a proper base case, the program can run out of stack space and cause a stack overflow.
Performance Overhead: Recursive functions can be slower than their iterative counterparts because each function call requires additional overhead, such as pushing data onto the call stack and managing the function’s state.
Stack Overflow: If the base case is missing or incorrectly defined, or if the recursion goes too deep, it could lead to a stack overflow error, which occurs when the call stack exceeds its limit.

Recursion vs Iteration

In many cases, recursion can be replaced by an iterative approach, especially when memory usage or performance is a concern. However, recursive functions tend to be more elegant and simpler to write when the problem is inherently recursive.

Iterative Approach: Uses loops (for/while) to repeat a task until a condition is met.
Recursive Approach: The function calls itself repeatedly, often with modified parameters, until a base case is reached.

While recursion can lead to more elegant code, iteration can often be more efficient in terms of both speed and memory.

Example: Walking Recursively and Iteratively

To demonstrate the difference between recursion and iteration, let’s implement a simple walking function that simulates a person taking steps.

Iterative Approach:
- We use a for loop to repeat the action of taking steps.
- The number of steps is passed as an argument, and the loop runs until the given number of steps is reached.
```
void walk(int steps) {
    for (int i = 0; i < steps; i++) {
        std::cout << "You take a step" << std::endl;
    }
}
 
```
Recursive Approach:
- In the recursive approach, we keep calling the walk function with a smaller number of steps (steps-1) until the base case is met.
- Base case: Stop when no steps are left (i.e., steps == 0).
```
void walk(int steps) {
    if (steps > 0) {
        std::cout << "You take a step" << std::endl;
        walk(steps - 1); // Recursive call
    }
}
 
```

Recursion simplifies the logic, but there is a trade-off in terms of memory and performance.

Example: Factorial (Recursive and Iterative)

Another classic example of recursion is calculating the factorial of a number. The factorial of a number n is the product of all positive integers less than or equal to n. The recursive definition of factorial is:

factorial(n) = n * factorial(n-1) (until n == 1).

1. Iterative Approach:

Using a for loop to compute the factorial iteratively.

int factorial(int num) {
    int result = 1;
    for (int i = 1; i <= num; i++) {
        result *= i;
    }
    return result;
}

2. Recursive Approach:

The recursive version of the factorial function calls itself until it reaches the base case (num == 1).

int factorial(int num) {
    if (num > 1) {
        return num * factorial(num - 1);  // Recursive call
    } else {
        return 1;  // Base case
    }
}

Base Case: factorial(1) = 1. This is crucial to prevent infinite recursion.

Factorial Example Explanation:

For factorial(5), the recursive approach will perform the following calls:

factorial(5) → 5 * factorial(4)
factorial(4) → 4 * factorial(3)
factorial(3) → 3 * factorial(2)
factorial(2) → 2 * factorial(1)
factorial(1) → returns 1 (base case)

The function calls “unwind,” multiplying the values to produce the result 120.

Recursion in Sorting and Searching Algorithms

Recursion is often used in sorting algorithms like QuickSort and MergeSort, and in searching algorithms like Binary Search. These problems naturally break into smaller sub-problems, which is ideal for recursive solutions.

For example:

QuickSort: Recursively divides the array into sub-arrays and sorts them.
MergeSort: Recursively splits the array in half, sorts each half, and then merges the results.

Recursion simplifies the implementation of these algorithms by breaking them into smaller sub-problems, which are easier to manage and implement.

Infinite Recursion and Stack Overflow

If a recursive function lacks a base case or if the base case is not reached properly, the function will keep calling itself indefinitely. This leads to an infinite recursion, which can cause a stack overflow error.

Stack Overflow occurs because each function call adds a new stack frame (containing local variables and information) to the call stack. When the stack grows too large (due to too many recursive calls), it exceeds the system’s memory limit and results in a crash.

Example of Infinite Recursion:

If the walk function doesn’t have a base case, it will recurse infinitely:

void walk(int steps) {
    std::cout << "You take a step" << std::endl;
    walk(steps); // Infinite recursion
}

In such cases, the program will run out of stack space and crash.

Conclusion

Recursion is a powerful tool for solving problems that have a recursive nature, like tree traversals, mathematical problems (e.g., factorial), and more.
While recursion can lead to more elegant and readable code, it may also lead to memory and performance issues, especially for large datasets or deep recursions.
It’s important to ensure that a base case is defined to avoid infinite recursion and potential stack overflow errors.

In general, the choice between recursion and iteration depends on the problem you’re solving. Recursion is often the clearer and simpler approach for problems that involve repeatedly breaking down tasks, but it comes with trade-offs in terms of performance and memory.

References

Video

Quartz 4

Explorer

C++ recursion explained easy 😵