DSA Masterclass Module 9: Recursion & Backtracking

Introduction to Recursion

Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem.

Every recursive function must have:

Base Case: The condition where the recursion stops.
Recursive Step: The part where the function calls itself with a smaller input.

1. Real-World Intuition: Russian Nesting Dolls

Imagine a set of Matryoshka dolls. To reach the tiny doll in the center, you must open the largest doll, then the one inside that, and so on. Opening each doll is the recursive step. The tiny solid doll at the center is the base case.

2. Curriculum in this Module

Theory & Intuition (Current Page)
Lesson: Backtracking Patterns - Generating permutations and combinations.
Problem: Permutations - Decision trees in action.
Problem: Combination Sum - Pruning the search space.
Curated Practice Problems - 10 essential challenges.

3. The Backtracking Template

Backtracking is "Recursion with a twist." We explore a path, and if it fails, we undo our last step.

void backtrack(state, choices) {
    if (isSolution(state)) {
        add(state);
        return;
    }
    for (choice : choices) {
        if (isValid(choice)) {
            makeChoice(choice); // Choose
            backtrack(state, remainingChoices); // Explore
            undoChoice(choice); // Un-choose (Backtrack)
        }
    }
}

Final Takeaway

Backtracking is essentially a DFS on a Decision Tree. If you can visualize the tree of choices, you can solve any backtracking problem.