2. Advanced Algorithms

Conceptual Idea

Recursion is when a function calls itself to solve a smaller version of the same problem. Each call works on a reduced input until a base case is reached, at which point the function stops calling itself and returns.

Base Case and Recursive Case

Two parts are essential: the base case (where the function does not recurse) and the recursive case (where it calls itself). Forgetting the base case or not reducing the problem correctly leads to infinite recursion or stack overflow.

Where It Shines

Recursion fits naturally for problems defined in terms of smaller subproblems, like tree traversals, divide‑and‑conquer algorithms, and some combinatorial tasks (permutations, combinations).

Strategy Overview

Divide and conquer breaks a problem into smaller subproblems, solves each recursively, and then combines the results. Classic examples include merge sort and quicksort.

Steps: Divide, Conquer, Combine

The “divide” step splits the input into parts; the “conquer” step recursively solves each part; the “combine” step merges or aggregates the partial results. This strategy often leads to efficient algorithms with good time complexity.

Benefits and Trade-offs

Divide and conquer can greatly reduce time complexity compared to naive methods, but often at the cost of more memory for recursion or temporary structures. It is a key pattern in algorithm design.

Dynamic programming (DP) is about solving problems by breaking them into overlapping subproblems and storing their solutions. Instead of recomputing the same result many times, you cache it in a table (memoization or tabulation).

Top‑down DP uses recursion with memoization: compute a result when needed and store it. Bottom‑up DP builds the table iteratively from smaller subproblems up to the final answer. Both approaches use the same core idea of reuse.

DP is especially useful for optimization and counting problems, such as shortest paths, knapsack, coin change, and sequence alignment. Recognizing overlapping subproblems and optimal substructure is the key.

Greedy algorithms build a solution step by step, making the locally optimal choice at each step and hoping it leads to a global optimum. They are simpler than DP but do not always yield the best solution.

Examples include interval scheduling, some minimum spanning tree algorithms, and coin change with specific denominations. Greedy algorithms usually require proof that a local choice strategy is globally optimal for the given problem.

Use greedy when you can prove that taking the best immediate option at each step leads to the overall best result. If you cannot prove this, dynamic programming or exhaustive methods are safer.

Backtracking explores all possible solutions by building them incrementally and abandoning partial solutions (“backtracking”) when they are clearly invalid or incomplete. It is a depth‑first search in solution space.

Backtracking is popular for constraint problems such as Sudoku, N‑Queens, and combinatorial puzzles. Pruning (stopping early when constraints are violated) is crucial to keep the search feasible.

Backtracking can still be expensive for large problems, but it is more efficient than a naive brute force search. It is also conceptually simple and often easier to implement than DP for some combinatorial tasks.