Recursion and backtracking: free-recall review
Free-recall prompts across the recursion unit. Answer each in your own words first, then reveal the model answer and compare.
Retrieval beats re-reading. For each prompt, say or write a full answer from memory before you open the model answer. The effort of pulling it back is what makes it stick.
Reconstruct the unit’s core mechanisms from memory: the two mandatory parts of a recursion, how the call stack turns depth into space, how a recursion tree turns branching into time, and the backtracking template with pruning.
- 01What are the two mandatory parts of any recursive function, and what goes wrong if either is missing?
- 02Explain the recursive leap of faith and why it makes recursive code easier to write.
- 03How does the call stack determine the space complexity of a recursive function, and what is a stack overflow?
- 04How do you read the time complexity of a recursive function from its recursion tree?
- 05State the backtracking template and explain why the undo step is mandatory.
- 06What is pruning in backtracking, and how do subsets, permutations, and combinations differ within the same template?
If you reconstructed each answer from memory, you hold the unit’s spine: a base case plus genuine progress make recursion terminate; the call stack turns maximum depth into O(depth) space; the recursion tree turns the branching factor and depth into b^d time; and backtracking is that recursive skeleton applied as choose-explore-undo, with pruning to skip doomed branches and copies to record results safely. Subsets, permutations, and combinations are the same template with different choice rules.
Something unclear?
Ask a question about this lesson. Questions are anonymous and go straight to the author to make the lesson better.