These are the notes for C Coding Questions, episode 23, placement practice for people who finished the SyntaxPilot C course. Recursion questions, part two: the Tower of Hanoi (and why it takes 2^n − 1 moves), all permutations of a string with backtracking (including repeated letters), and binary search written recursively.
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, glibc, Linux x86-64: 4-byte int, 8-byte long long), the SyntaxPilot compiler's C command with warnings on, and every output below is real. In the input lines below, ⏎ means pressing Enter.
Real-life pictures
| In real life | In C |
|---|---|
| a temple puzzle: 64 golden disks to move, one at a time, never a big one on a small one | the Tower of Hanoi, 2^n − 1 moves |
| seating guests in a row of chairs: choose who sits first, then seat the rest | permutations: fix one position, permute the rest |
| a guest gets up again so you can try the next one | backtracking: undo the choice after exploring it |
| finding a word in a dictionary: open the middle, keep one half | binary search, the same search on half the range |
The mindset: trust the smaller call
Last episode: every recursive function has a base case and a recursive case that moves towards it. This episode adds one more habit: don't trace every call in your head. Assume the call on the smaller input already works (the "recursive leap of faith"), and only check that (1) the base case is right and (2) you combine the smaller answers correctly. Then test on small inputs with a real check.
Q1: Tower of Hanoi
Problem. n disks sit on peg A, biggest at the bottom. Move them all to peg C, using peg B. Rules: move one disk at a time, only the top disk of a peg, and never put a bigger disk on a smaller one. Print every move.
Think out loud.
- n = 3 needs 7 moves. n = 1: one move, A → C. n = 0: nothing.
- Think only about the biggest disk. To move it from A to C, the n − 1 disks above it must first go out of the way, to B: 1. move n − 1 disks from A to B (C helps), 2. move the biggest disk from A to C, 3. move the n − 1 disks from B to C (A helps).
- Steps 1 and 3 are the same puzzle with one disk fewer: recursion. Base case: 0 disks, do nothing.
The obvious attempt (with a move checker)
To test the moves for real, the program keeps the pegs as stacks of disks. move prints ILLEGAL if the peg is empty or a bigger disk lands on a smaller one. Step 3 is written the way many people first write it from memory:
#include <stdio.h>
int peg[3][20], top[3]; /* three pegs, each a stack of disks */
long long moves = 0;
void move(int from, int to) {
if (top[from] == 0) {
printf("ILLEGAL: peg %c is empty\n", 'A' + from);
return;
}
int d = peg[from][--top[from]];
if (top[to] > 0 && peg[to][top[to] - 1] < d)
printf("ILLEGAL: disk %d onto disk %d\n", d, peg[to][top[to] - 1]);
peg[to][top[to]++] = d;
moves++;
printf("disk %d: %c -> %c\n", d, 'A' + from, 'A' + to);
}
void hanoi(int n, int from, int to, int via) {
if (n == 0) return;
hanoi(n - 1, from, via, to);
move(from, to);
hanoi(n - 1, from, to, via);
}
int main() {
int n;
scanf("%d", &n);
for (int d = n; d >= 1; d--) peg[0][top[0]++] = d;
hanoi(n, 0, 2, 1);
printf("%lld moves, disks on peg C: %d\n", moves, top[2]);
return 0;
}
Input 3⏎:
disk 1: A -> C
disk 2: A -> B
ILLEGAL: disk 3 onto disk 2
disk 3: A -> B
ILLEGAL: peg A is empty
ILLEGAL: peg A is empty
ILLEGAL: peg A is empty
ILLEGAL: peg A is empty
3 moves, disks on peg C: 1
Why it failed
Step 3 says "move n − 1 disks from A again". But step 1 parked them on B (the via peg). So it takes disks from the wrong peg. Step 3 must be hanoi(n - 1, via, to, from): from B to C, with A helping.
The fix
Only the last line of hanoi changes:
void hanoi(int n, int from, int to, int via) {
if (n == 0) return;
hanoi(n - 1, from, via, to); /* 1. n-1 disks out of the way, to via */
move(from, to); /* 2. the biggest disk */
hanoi(n - 1, via, to, from); /* 3. n-1 disks from via onto it */
}
Input 3⏎:
disk 1: A -> C
disk 2: A -> B
disk 1: C -> B
disk 3: A -> C
disk 1: B -> A
disk 2: B -> C
disk 1: A -> C
7 moves, disks on peg C: 3
Seven legal moves, all three disks on C. Disk 1 moves on every other move.
How many moves? 2^n − 1
moves(n) = moves(n − 1) + 1 + moves(n − 1) = 2 × moves(n − 1) + 1, and moves(0) = 0. This kind of equation, which defines a value from smaller values, is called a recurrence.
| n | 1 | 2 | 3 | 4 | 5 | 10 | 20 | 64 |
|---|---|---|---|---|---|---|---|---|
| moves | 1 | 3 | 7 | 15 | 31 | 1,023 | 1,048,575 | 2^64 − 1 |
Each is one less than a power of two: moves(n) = 2^n − 1 (adding 1 to both sides: moves(n) + 1 = 2 × (moves(n − 1) + 1)).
2^64 − 1 doesn't fit in a long long (its maximum is 2^63 − 1). An unsigned long long has no negative numbers, so it goes up to 2^64 − 1; print it with %llu.
#include <stdio.h>
unsigned long long count_moves(int n) {
if (n == 0) return 0;
return 2 * count_moves(n - 1) + 1; /* n-1 disks, the big one, n-1 again */
}
int main() {
int n;
while (scanf("%d", &n) == 1)
printf("moves(%2d) = %llu\n", n, count_moves(n));
return 0;
}
Input 1 2 3 4 10 20 64⏎:
moves( 1) = 1
moves( 2) = 3
moves( 3) = 7
moves( 4) = 15
moves(10) = 1023
moves(20) = 1048575
moves(64) = 18446744073709551615
At one move per second, 64 disks take about 585 billion years.
Complexity. Printing every move: O(2^n) time, and that's the minimum possible (2^n − 1 moves are needed). Stack depth: O(n), because each call waits for only one smaller call at a time. count_moves itself is O(n).
Q2: All permutations of a string
Problem. Print every permutation (ordering of all the letters) of a string, and count them.
Think out loud.
abc→abc acb bac bca cba cab: 3 × 2 × 1 = 3! = 6.- Recursively: for position k, try each remaining letter there (swap it into position k), then permute positions k + 1 … n − 1. When k = n, print.
- Edge cases: one letter (1 permutation); repeated letters (
aabhas only 3 different ones); long strings (n! grows very fast: 10! = 3,628,800).
The obvious attempt: swap and recurse
#include <stdio.h>
#include <string.h>
int count = 0;
void swap(char *a, char *b) { char t = *a; *a = *b; *b = t; }
void permute(char *s, int k, int n) {
if (k == n) { /* every position is fixed */
printf("%s ", s);
count++;
return;
}
for (int i = k; i < n; i++) {
swap(&s[k], &s[i]); /* put s[i] at position k */
permute(s, k + 1, n);
}
}
int main() {
char s[20];
while (scanf("%19s", s) == 1) {
count = 0;
printf("%s: ", s);
permute(s, 0, strlen(s));
printf("-> count = %d\n", count);
}
return 0;
}
Input abc⏎:
abc: abc acb cab cba abc acb -> count = 6
The count is 6, but abc and acb appear twice, and bac and bca are missing.
Why it failed
The swaps made inside a call are still in the string when the call returns. So the loop's next swap works on a scrambled string, not the one it started with.
Fix 1: backtracking (swap back)
After the recursive call, swap the two letters back, so the string is exactly as before. Choose, explore, undo: this is backtracking.
for (int i = k; i < n; i++) {
swap(&s[k], &s[i]); /* put s[i] at position k */
permute(s, k + 1, n);
swap(&s[k], &s[i]); /* undo: backtrack */
}
Input abc aab⏎:
abc: abc acb bac bca cba cab -> count = 6
aab: aab aba aab aba baa baa -> count = 6
abc is now right. But aab prints each of its 3 permutations twice.
Fix 2: skip a letter already tried at this position
At position 0 we try the first a and later the second a: the same choice, so the same results. Keep a tried list per call (one flag for each of the 256 possible char values). Using the letter as an unsigned char makes its value 0 … 255, a safe index even for non-ASCII bytes.
#include <stdio.h>
#include <string.h>
int count = 0;
void swap(char *a, char *b) { char t = *a; *a = *b; *b = t; }
void permute(char *s, int k, int n) {
if (k == n) { /* every position is fixed */
if (n <= 4) printf("%s ", s);
count++;
return;
}
int tried[256] = {0}; /* letters already used at position k */
for (int i = k; i < n; i++) {
unsigned char c = s[i];
if (tried[c]) continue; /* same letter here again: skip */
tried[c] = 1;
swap(&s[k], &s[i]);
permute(s, k + 1, n);
swap(&s[k], &s[i]); /* undo: backtrack */
}
}
int main() {
char s[20];
while (scanf("%19s", s) == 1) {
count = 0;
printf("%s: ", s);
permute(s, 0, strlen(s));
printf("-> count = %d\n", count);
}
return 0;
}
Input abc aab x banana abcdefghij⏎ (words longer than 4 letters are counted, not printed):
abc: abc acb bac bca cba cab -> count = 6
aab: aab aba baa -> count = 3
x: x -> count = 1
banana: -> count = 60
abcdefghij: -> count = 3628800
With repeated letters the count is n! divided by (count of each letter)!: aab → 3!/2! = 3, banana (a×3, n×2, b×1) → 6!/(3! × 2!) = 60. Ten different letters: 10! = 3,628,800, in about 0.2 seconds.
Complexity. n! permutations, each printed in O(n): O(n × n!) time. That's the size of the output, so no method can be faster. Stack depth O(n), plus a 256-int tried array (1 KB) per level.
Q3: Binary search, recursively
Problem. In a sorted array, return the index of x, or −1 if it's not there. (Episode 12 did it with a loop.)
Think out loud.
- Array
2 5 8 12 16 23 38 56 72 91: 16 → 4, 23 → 5, 91 → 9, 2 → 0, 40 → −1. - Look at the middle: equal → done; smaller than x → search the right half; bigger → the left half.
- Edge cases: the first and last element; a value that's missing (inside the range, below it, above it); one element.
The obvious attempt: pass a pointer to the half
#include <stdio.h>
int search(int *a, int n, int x) { /* look in a[0 .. n-1] */
if (n == 0) return -1;
int mid = n / 2;
if (a[mid] == x) return mid;
if (a[mid] < x) return search(a + mid + 1, n - mid - 1, x);
return search(a, mid, x);
}
int main() {
int a[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int x;
while (scanf("%d", &x) == 1)
printf("search %d -> index %d\n", x, search(a, 10, x));
return 0;
}
Input 16⏎23⏎91⏎2⏎40⏎:
search 16 -> index 1
search 23 -> index 5
search 91 -> index 0
search 2 -> index 0
search 40 -> index -1
16 is at index 4, and 91 at index 9. 23 and 2 are right only because they were found before any right-half call, and 40 because −1 needs no offset.
Why it failed
a + mid + 1 is the address where the right half starts, so the recursive call searches a smaller array and answers with an index inside that smaller array. For 16: the whole array's middle is 23 (index 5), so the left half 2 5 8 12 16 is searched; its middle is 8 (index 2), so the right half starts at a[3], and 16 is found at index 1 of that half. The real index is 3 + 1 = 4.
You could add the offset back (mid + 1 + r), but only when r != -1, otherwise −1 + offset becomes a wrong "found". It's easy to get wrong.
The fix: keep the whole array, pass lo and hi
lo and hi are the lowest and highest index where x could still be. Every index then refers to the same array. Base case: lo > hi means the range is empty, so −1. The middle is lo + (hi - lo) / 2, which can't overflow (episode 12).
#include <stdio.h>
int calls = 0;
int big[1000000];
int search(int *a, int lo, int hi, int x) { /* look in a[lo .. hi] */
calls++;
if (lo > hi) return -1; /* empty range: not found */
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) return mid;
if (a[mid] < x) return search(a, mid + 1, hi, x);
return search(a, lo, mid - 1, x);
}
int main() {
int a[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int x;
while (scanf("%d", &x) == 1) {
calls = 0;
int i = search(a, 0, 9, x);
printf("search %d -> index %d, calls = %d\n", x, i, calls);
}
for (int i = 0; i < 1000000; i++) big[i] = 2 * i;
calls = 0;
int i = search(big, 0, 999999, 1999998);
printf("1,000,000 numbers: index %d, calls = %d\n", i, calls);
return 0;
}
Input 16⏎23⏎91⏎2⏎40⏎1⏎100⏎:
search 16 -> index 4, calls = 1
search 23 -> index 5, calls = 3
search 91 -> index 9, calls = 4
search 2 -> index 0, calls = 3
search 40 -> index -1, calls = 5
search 1 -> index -1, calls = 4
search 100 -> index -1, calls = 5
1,000,000 numbers: index 999999, calls = 20
(big is a global array: 4 MB as a local would use half the stack.)
Complexity. The range halves every call: O(log n) time and O(log n) stack depth (20 calls for a million). The loop version from episode 12 is O(1) space, so in real code the loop is slightly better; interviewers often ask for both. Every recursive call here is a tail call (the last thing the function does), so gcc at -O2 can turn it into a loop.
Complexity summary
| Problem | Calls per level | Time | Stack depth | Example |
|---|---|---|---|---|
| Tower of Hanoi | 2 calls on n − 1 | O(2^n) | O(n) | 64 disks: 2^64 − 1 moves |
| count_moves | 1 call on n − 1 | O(n) | O(n) | |
| permutations | up to n calls on n − 1 | O(n × n!) | O(n) | 10 letters: 3,628,800 |
| binary search | 1 call on half | O(log n) | O(log n) | 10^6 numbers: 20 calls |
Rule of thumb: two calls on n − 1 → 2^n; one call on n / 2 → log n; n choices, then n − 1, … → n!.
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
Hanoi step 3 hanoi(n-1, from, to, via) |
ILLEGAL: disk 3 onto disk 2, ILLEGAL: peg A is empty |
the n − 1 disks are on via |
hanoi(n-1, via, to, from) |
long long for 2^64 − 1 |
overflow (UB) | its maximum is 2^63 − 1 | unsigned long long, %llu |
%d or %lld for an unsigned long long |
a wrong (negative) number, and a -Wformat warning for %d |
wrong format | %llu |
| permutations without swapping back | abc acb cab cba abc acb |
the string stays scrambled | swap back: backtrack |
| repeated letters | aab printed 6 times |
the same letter tried twice at one position | a tried list per position |
char as an array index |
a negative index for bytes ≥ 128 (UB) | char may be signed |
unsigned char c = s[i]; |
recursive search on a + mid + 1 |
search 16 -> index 1 |
index inside the smaller array | pass lo and hi |
no lo > hi base case |
endless calls / a crash for a missing x | the search never stops | if (lo > hi) return -1; |
mid instead of mid + 1 / mid - 1 |
endless calls when x is missing | the range stops shrinking | exclude mid |
Your turn: all subsets of a string (solution)
Problem. Print every subset of the letters of a string (keeping their order), including the empty one. abc → "" c b bc a ac ab abc: 2^3 = 8 subsets.
Idea. For each letter there are two choices: leave it out, or take it; then decide the rest. That's a binary decision tree with 2^n leaves. Keep the letters taken so far in out; "undo" is free here because len is passed by value. O(n × 2^n) time, O(n) depth.
Show the solution
#include <stdio.h>
#include <string.h>
int count = 0;
/* s: the letters, k: the next letter to decide, out: letters taken so far, len: how many */
void subsets(const char *s, int k, char *out, int len) {
if (s[k] == '\0') { /* every letter decided */
out[len] = '\0';
printf("\"%s\" ", out);
count++;
return;
}
subsets(s, k + 1, out, len); /* leave s[k] out */
out[len] = s[k]; /* take s[k] ... */
subsets(s, k + 1, out, len + 1); /* ... and decide the rest */
}
int main() {
char s[20], out[20];
while (scanf("%19s", s) == 1) {
count = 0;
subsets(s, 0, out, 0);
printf("-> count = %d\n", count);
}
return 0;
}
Input abc⏎x⏎:
"" "c" "b" "bc" "a" "ac" "ab" "abc" -> count = 8
"" "x" -> count = 2
Practice questions (with solutions)
1. Hanoi with 4 disks: list the 15 moves.
Solution
A short version without the checker (pegs as letters):
#include <stdio.h>
void hanoi(int n, char from, char to, char via) {
if (n == 0) return;
hanoi(n - 1, from, via, to);
printf("disk %d: %c -> %c\n", n, from, to);
hanoi(n - 1, via, to, from);
}
int main() { hanoi(4, 'A', 'C', 'B'); return 0; }
disk 1: A -> B
disk 2: A -> C
disk 1: B -> C
disk 3: A -> B
disk 1: C -> A
disk 2: C -> B
disk 1: A -> B
disk 4: A -> C
disk 1: B -> C
disk 2: B -> A
disk 1: C -> A
disk 3: B -> C
disk 1: A -> B
disk 2: A -> C
disk 1: B -> C
The middle move (move 8 = 2^3) is always the biggest disk.
2. Permutations in sorted (dictionary) order, without duplicates.
Solution
Sort the letters first, then build the answer left to right, picking unused letters smallest first. Skip a letter equal to the previous one when the previous one is unused (that copy would give the same results).
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* sorted order: choose the next letter from the unused ones, smallest first */
void perm_sorted(const char *s, int n, int *used, char *out, int k) {
if (k == n) { out[n] = '\0'; printf("%s ", out); return; }
for (int i = 0; i < n; i++) {
if (used[i]) continue;
if (i > 0 && s[i] == s[i - 1] && !used[i - 1]) continue; /* skip repeats */
used[i] = 1; out[k] = s[i];
perm_sorted(s, n, used, out, k + 1);
used[i] = 0; /* backtrack */
}
}
int cmp(const void *a, const void *b) { return *(const char *)a - *(const char *)b; }
int main() {
char s[20], out[20];
int used[20];
while (scanf("%19s", s) == 1) {
int n = strlen(s);
qsort(s, n, 1, cmp);
memset(used, 0, sizeof used);
perm_sorted(s, n, used, out, 0);
printf("\n");
}
return 0;
}
Input cba⏎aab⏎:
abc acb bac bca cab cba
aab aba baa
(The comparator subtracts two char values, which can't overflow an int, unlike the int subtraction bug from episode 14.)
3. First occurrence of x in a sorted array, recursively.
Solution
When a[mid] == x, there may be another x further left, so search the left part; if it finds nothing, mid is the first.
#include <stdio.h>
int first(const int *a, int lo, int hi, int x) { /* first index of x in a[lo..hi], or -1 */
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (a[mid] < x) return first(a, mid + 1, hi, x);
if (a[mid] > x) return first(a, lo, mid - 1, x);
int left = first(a, lo, mid - 1, x); /* a[mid] == x: is there one further left? */
return left != -1 ? left : mid;
}
int main() {
int a[] = {1, 3, 3, 3, 5, 7, 7, 9};
int x;
while (scanf("%d", &x) == 1)
printf("first %d -> %d\n", x, first(a, 0, 7, x));
return 0;
}
Input 3 7 1 9 4 10 0⏎:
first 3 -> 1
first 7 -> 5
first 1 -> 0
first 9 -> 7
first 4 -> -1
first 10 -> -1
first 0 -> -1
Still one call per level: O(log n).
Quick quiz
#include <stdio.h>
void f(int n) {
if (n == 0) return;
f(n - 1);
printf("%d\n", n);
f(n - 1);
}
int main() {
f(10);
return 0;
}
How many lines does it print? (A) 1023 (B) 1024 (C) 20 (D) 100
Answer
(A) 1023. lines(n) = 2 × lines(n − 1) + 1 and lines(0) = 0: exactly the Hanoi recurrence, so 2^10 − 1 = 1023. (Counted for real: ./main | wc -l prints 1023.) It prints the "ruler" sequence 1 2 1 3 1 2 1 4 …, which is also which disk moves at each step of Hanoi.
Interview questions
- Explain the Tower of Hanoi recursion. Move n − 1 disks to the spare peg, move the biggest, move the n − 1 back on top; base case 0 disks.
- Minimum moves for n disks? Why can't it be fewer? 2^n − 1. The biggest disk must move at least once, and before that all n − 1 others must be off it and off the target peg; after, they must come back: at least 2 × (moves for n − 1) + 1.
- How many permutations does a string of n distinct letters have? With repeats? n!; n! divided by the factorial of each letter's count.
- What is backtracking? Build a solution step by step; after exploring a choice, undo it and try the next.
- How do you avoid duplicate permutations? A per-position "tried" set, or sort and skip equal neighbours.
- Recursive vs iterative binary search? Same O(log n) time; recursion uses O(log n) stack, the loop O(1).
- Why
lo + (hi - lo) / 2?(lo + hi) / 2can overflow for big indexes. - What's the recursion depth of permutations and Hanoi? n.
- What is a recurrence? An equation that defines a value from smaller values: T(n) = 2T(n − 1) + 1.
- Subsets vs permutations count? 2^n subsets; n! permutations.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Tower of Hanoi | Puzzle: move a stack of disks peg to peg, never big on small | 3 disks: 7 moves |
| Peg | One of the three poles (A, B, C) | hanoi(n, 0, 2, 1) |
| Recurrence | An equation defining a value from smaller ones | moves(n) = 2 moves(n − 1) + 1 |
| 2^n − 1 | The minimum Hanoi moves for n disks | 2^10 − 1 = 1023 |
unsigned long long |
A 64-bit integer with no negative values, up to 2^64 − 1 | %llu |
| Recursive leap of faith | Trust that the smaller call works; check the base case and the combining | Hanoi's steps 1 and 3 |
| Permutation | One ordering of all the items | bca is a permutation of abc |
| n! | The number of orderings of n distinct items | 3! = 6 |
| Backtracking | Choose, explore, undo, then try the next choice | swap, permute, swap back |
tried[256] |
One flag per possible char value |
skip a repeated letter |
unsigned char |
A char read as 0..255, safe as an array index |
tried[c] |
| Subset | Any selection of the items, order kept | ac of abc |
| Binary search | Halve a sorted range until x is found or the range is empty | 20 calls for 10^6 |
lo, hi |
The lowest and highest index still possible | search(a, lo, hi, x) |
| Empty range | lo > hi: nowhere left to look |
return −1 |
| Offset | Where a sub-array starts inside the whole array | a + mid + 1 |
| Tail call | A call that is the last thing a function does | return search(...) |
| Divide and conquer | Solve a problem through smaller pieces of it | binary search, Hanoi |
Summary
- Hanoi: n − 1 disks out of the way, the biggest disk, n − 1 disks back on top. Step 3 starts from the via peg. Moves = 2^n − 1:
unsigned long longfor 64 disks. Test recursion with a real checker. - Permutations: fix position k (swap each candidate in), permute the rest, swap back (backtracking). Skip letters already tried at that position to avoid duplicates. O(n × n!).
- Recursive binary search: pass
loandhion the whole array; base caselo > hi. O(log n) time and depth. - Count the calls per level to estimate the cost: two calls on n − 1 → 2^n; one call on half → log n.
Next episode: Structure questions: student records sorted by marks, adding complex numbers, and days between two dates (leap years).