Recursion is a problem-solving method where a function solves a smaller version of the same problem. Backtracking is a recursive search technique that builds a solution step by step and undoes choices that cannot work. Students need this cheat sheet to recognize recursive patterns, trace call stacks, and write correct stopping conditions.
These skills are essential for algorithms such as tree traversal, maze solving, permutations, and constraint problems.
Key Facts
- Every recursive function needs a base case, such as if n == 0 return 1, to stop infinite calls.
- A recursive case must move toward the base case, such as factorial(n) = n * factorial(n - 1).
- The call stack stores unfinished function calls, and the most recent call returns before earlier calls continue.
- A common recursion pattern is solve(input) = solve(smaller input) + combine result.
- Backtracking follows the pattern choose, explore, unchoose to test possible solutions without permanently keeping bad choices.
- A decision tree with branching factor b and depth d can have up to b^d possible paths.
- The time complexity of many backtracking algorithms is exponential, such as O(2^n) for subsets or O(n!) for permutations.
- A recursive function that calls itself once per level with n decreasing by 1 usually has recursion depth O(n).
Vocabulary
- Recursion
- Recursion is when a function calls itself to solve a smaller version of the same problem.
- Base Case
- A base case is the condition that stops recursion and returns a direct answer.
- Recursive Case
- A recursive case is the part of a function that makes a smaller self-call and uses its result.
- Call Stack
- The call stack is the memory structure that keeps track of active function calls and their local variables.
- Backtracking
- Backtracking is a search method that tries a choice, explores it, and then undoes the choice if needed.
- Pruning
- Pruning is skipping branches of a search tree that cannot lead to a valid or better solution.
Common Mistakes to Avoid
- Missing the base case causes infinite recursion because the function never reaches a stopping condition.
- Writing a recursive call that does not reduce the problem size is wrong because the function may repeat the same input forever.
- Forgetting to unchoose in backtracking leaves old choices in the current state, which can corrupt later branches of the search.
- Returning too early inside a loop can stop backtracking before all possible choices have been explored.
- Confusing recursion depth with total work is incorrect because a depth of O(n) can still produce O(2^n) or O(n!) total calls.
Practice Questions
- 1 How many times is factorial called when computing factorial(5) using factorial(n) = n * factorial(n - 1) with base case factorial(0) = 1?
- 2 A backtracking algorithm generates all subsets of a list with 4 elements. How many subsets should it produce?
- 3 Write pseudocode for a recursive function sum(n) that returns 1 + 2 + ... + n and uses sum(0) = 0 as the base case.
- 4 Explain why the unchoose step is necessary in a backtracking algorithm that builds combinations.