Recursion & Backtracking Exercises: Practice Problems
Time to practice recursion. For each problem, identify the base case and the recursive case first, then write the code and trace a small input by hand. Reason about the time and space cost — remember the call stack counts toward space. Only then open the answer sheet. Every View answer link jumps to a full multi-language solution on the recursion solutions page.
How to practice: If you’re stuck, re-read base & recursive cases or the backtracking template before peeking. State your recurrence before you code — it forces clarity.
Warm-ups
Q1. Factorial. Compute n! recursively. Define the base case and the recursive case explicitly. State the time and space complexity.
Q2. Sum of digits. Given a non-negative integer, return the sum of its digits using recursion (e.g. 1234 → 10). Hint: the last digit is n % 10 and the rest is n / 10.
Q3. Fast power. Compute x raised to the power n (integer n ≥ 0) in O(log n) time using exponentiation by squaring, not a naive O(n) loop.
Core problems
Q4. Generate all subsets. Given a list of distinct integers, return every subset (the power set). For n elements there are 2ⁿ subsets. Use the choose/skip recursion.
Q5. Generate all permutations. Given a list of distinct integers, return every ordering. There are n! of them. Use backtracking with a used marker.
Challenge
Q6. Generate parentheses. Given n, generate all strings of n pairs of balanced parentheses (e.g. n = 2 → ["(())", "()()"]). Prune any prefix that can’t become valid.
Q7. Merge sort. Sort an array using divide and conquer: split in half, sort each half recursively, and merge. Target O(n log n) time.
Done? Review every solution on the recursion answer sheet — even the ones you solved, since there’s often a cleaner formulation. Then continue to sorting.