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’s a powerful tool for tackling problems that can be broken down into similar sub-problems, such as tree traversals, divide-and-conquer algorithms, and combinatorial problems.

How the Algorithm Works

Here’s how recursion works:

1. Base Case: Define a condition under which the recursion stops. Without a base case, the recursion would continue indefinitely, leading to a stack overflow.
2. Recursive Case: Break the problem into smaller instances and solve them by calling the same function.
3. Return Values: Use return statements to propagate results back through the call stack.

For example, calculating the factorial of a number involves breaking it down as n! = n * (n-1)! until the base case of 0! = 1.

Time & Space Complexities

• Time Complexity: Depends on the number of recursive calls. For example:
  • Factorial: O(n)
  • Fibonacci (Naive): O(2^n) (can be reduced with memoization)
• Space Complexity: O(n) due to the recursion stack, where n is the depth of the recursive calls.

When to Use

Recursion is ideal for problems that can be divided into smaller, self-similar sub-problems, such as:

• Divide-and-conquer algorithms (e.g., Merge Sort, Quick Sort)
• Tree traversals (e.g., Inorder, Preorder, Postorder)
• Dynamic programming (e.g., Fibonacci with memoization)
• Combinatorial problems (e.g., Permutations, Subsets)

It’s essential to ensure the base case is well-defined to avoid infinite recursion.

Code Example

#include <iostream>
using namespace std;

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

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is " << factorial(num) << endl;
    return 0;
}

Problems to Solve

WIP

Resources

• Recursion (Grokking Algorithms)