What this topic covers
18 subtopics- Tracing output6
- Backtracking5
- Basics5
- Permutations5
- Recurrences3
- Subsets3
- Divide and conquer2
- Grid recursion2
- N-Queens2
- Strings2
- Tail recursion2
- Tower of Hanoi2
Show all 18 subtopics
- Call counting1
- Call stack1
- Combinations1
- Memoisation1
- Mutual recursion1
- Recursive construction1
- Beginner 15
- Intermediate 15
- Advanced 15
About this topic
A recursive function solves a problem by calling itself on a smaller version and stopping at a base case. Output questions test whether you know when each line runs: code before the recursive call runs on the way down, code after it runs on the way back up. Backtracking builds a solution one choice at a time – choose, explore, un-choose – and abandons a branch as soon as it cannot work. Every program below was run to produce its answer.
Free preview
Sample questions
Try each one first, then open the answer for the explanation and why the other options are wrong.
What does this print?
#include <stdio.h>
void f(int n) {
if (n == 0) return;
printf("%d ", n);
f(n - 1);
}
int main(void) {
f(3);
printf("\n");
return 0;
}Show answer and explanation
Explanation
The print happens before the recursive call, so values appear on the way down: 3, 2, 1. f(0) returns without printing.
Why the other options are wrong
- Af(0) returns before printing.
- BThat would need the print after the call.
- DBoth order and the 0 are wrong.
How many moves does Tower of Hanoi make for 6 discs? The program prints it.
moves = 0
def hanoi(n, src, dst, via):
global moves
if n == 0:
return
hanoi(n - 1, src, via, dst)
moves += 1
hanoi(n - 1, via, dst, src)
hanoi(6, 'A', 'C', 'B')
print(moves)The answer is a number – work it out, then open the solution.
Show answer and explanation
Explanation
Move n − 1 discs out of the way, move the largest, move n − 1 back on top: T(n) = 2T(n − 1) + 1 = 2ⁿ − 1 = 63.
How many solutions does the 8-Queens problem have (counting rotations and reflections as different)?
The answer is a number – work it out, then open the solution.
Show answer and explanation
Explanation
92 solutions, of which 12 are fundamentally different up to symmetry. Using sets (or bitmasks) for columns and both diagonals makes each placement check O(1).