SyntaxPilot
Courses/C Coding Questions/Lesson 23
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C Coding Questions · Lesson 23 of 30

Recursion questions II

Tower of Hanoi (moves = 2^n - 1)all permutations of a stringrecursive binary search

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 (aab has 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

  1. 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.
  2. 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.
  3. How many permutations does a string of n distinct letters have? With repeats? n!; n! divided by the factorial of each letter's count.
  4. What is backtracking? Build a solution step by step; after exploring a choice, undo it and try the next.
  5. How do you avoid duplicate permutations? A per-position "tried" set, or sort and skip equal neighbours.
  6. Recursive vs iterative binary search? Same O(log n) time; recursion uses O(log n) stack, the loop O(1).
  7. Why lo + (hi - lo) / 2? (lo + hi) / 2 can overflow for big indexes.
  8. What's the recursion depth of permutations and Hanoi? n.
  9. What is a recurrence? An equation that defines a value from smaller values: T(n) = 2T(n − 1) + 1.
  10. 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 long for 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 lo and hi on the whole array; base case lo > 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).