Recursion Definition

Recursion is a programming concept where a function calls itself directly or indirectly to solve a problem. In DSA, recursion is often used to solve problems that can be broken down into smaller, similar sub-problems.

When a function calls itself until a specified condition is met.

Key Points:

• Base Case: Every recursive function must have a base case, which represents the simplest form
• Recursive Case: The function

Detailed Explanation

Recursion is a powerful technique in programming where a function solves a problem by calling itself with a smaller instance of the same problem. It breaks down a problem into smaller, more manageable sub-problems until a base case is reached. The base cases represents the simplest form of the problem and provides a termination condition for the recursion.

Let's understand the concept of recursion with an example of 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.

Example: Factorial Calculation

#include <iostream>
using namespace std;

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

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

In this example, the factorial function calculates the factorial of a number recursively. Let's break down the process:

1. The function factorial takes an integer n as input.
2. If n is 0 or 1, it returns 1, which is the base case.
3. Otherwise, it calculates n * factorial(n - 1), which is the recursive case.
4. This recursive call continues until n becomes 0 0r 1, and the base case is reached.
5. At this point, the recursion stops, and the function starts returning the values back up the call stack.
6. The final result is the factorial of the original input number.

Understanding Stack Overflow

While recursion offers many benefits, it's essential to be mindful of its limitations. One such limitation is the potential for stack overflow, a runtime error that occurs when the call stack exceeds its maximum size.

In C++, each function call consumes a certain amount of memory on the stack. This memory includes parameters, local variables, and the return address. When a function calls itself recursively without reaching the base case or without proper termination conditions, it keeps adding new stack frames, eventually exhausting the available stack space.

Consider the following example:

void infiniteRecursion() {
    infiniteRecursion();
}

In this function, there's no base case to stop the recursion. As a result, it will keep calling itself indefinitely, consuming stack space until the stack overflows.

Preventing Stack Overflow

To prevent stack overflow, it's crucial to ensure that recursive functions have well-defined base cases and termination conditions. These conditions should be carefully designed to ensure that the recursion stops after a finite number of steps.