Tower of Hanoi & accumulators

Overview

The Tower of Hanoi is the purest illustration of self-similarity: to move n disks, move the top n-1 elsewhere, move the largest disk, then move those n-1 back on top of it. The move count follows moves(n) = 2*moves(n-1) + 1, which solves to 2^n - 1 — exponential, and unavoidably so. The same lesson introduces the accumulator parameter: an extra argument that carries a running result down the recursion instead of building it up on the way back, turning the function tail-recursive and often simpler to reason about.

Why it matters

Hanoi teaches that recursion can express an exponential algorithm as three lines, which is both its power and its warning — elegance does not imply efficiency. Accumulators matter more practically: they are how you convert a recursion that builds its answer during unwinding into one that carries state forward, which is the standard shape for digit manipulation, list reversal, and parser state.

Core concepts

Self-similar decomposition. Moving n disks is defined entirely in terms of moving n-1 disks, twice, plus one direct move. There is no cleverer decomposition — the exponential count is inherent to the puzzle, not an artefact of the implementation.

The recurrence. moves(n) = 2*moves(n-1) + 1, moves(0) = 0. Unrolled that is 2^n - 1, so 64 disks would take about 1.8 x 10^19 moves.

Accumulator style. Compare building on the way up — rev(n) = ... + rev(n/10) — with carrying on the way down: rev(n, acc) = rev(n/10, acc*10 + n%10). The accumulator version has nothing left to do after the recursive call returns, which makes it tail-recursive.

Tail recursion is not free in C. A tail call can be optimised into a jump, but the C standard does not require it. Do not rely on constant stack usage; check your compiler and flags, or write a loop when depth matters.

Base case carries the answer. In accumulator style the base case returns the accumulator itself rather than a neutral value — a small shift that trips people up the first time.

Syntax notes

/* number of moves for n disks: 2^n - 1 */
long long hanoi(int n) {
    if (n <= 0) return 0;
    return 2 * hanoi(n - 1) + 1;
}

/* accumulator style: the answer is carried DOWN, not built up */
int rev(int n, int acc) {
    return (n == 0) ? acc : rev(n / 10, acc * 10 + n % 10);
}
/* call as rev(1234, 0) -> 4321 */

/* the actual moves, if you want them printed */
void hanoi_moves(int n, char from, char to, char via) {
    if (n == 0) return;
    hanoi_moves(n - 1, from, via, to);
    printf("move disk %d: %c -> %c\n", n, from, to);
    hanoi_moves(n - 1, via, to, from);
}

Key points:

• The base case in accumulator style returns acc, not 0.
• hanoi_moves swaps the auxiliary peg on each call — that rotation is the whole trick.
• long long: hanoi(63) overflows 32 bits comfortably.

Lesson

The Tower of Hanoi epitomizes recursion: to move n disks, move n-1, move the largest, then move n-1 back — moves(n)=2*moves(n-1)+1. Reversing a number's digits shows the accumulator technique: carry a running result down the recursion.

Code examples

#include <stdio.h>
static long long hanoi(int n){ if(n<=0) return 0; return 2*hanoi(n-1)+1; }
static int rev(int n,int acc){ return n==0 ? acc : rev(n/10, acc*10 + n%10); }
int main(void){
    printf("Tower of Hanoi with 10 disks needs %lld moves\n", hanoi(10));
    printf("reverse of 1230 = %d\n", rev(1230,0));
    return 0;
}

Line by line

Common mistakes

Forgetting the +1 in Hanoi; reversing digits without an accumulator argument.

Debugging tips

Compiler errors and warnings:

• warning: integer overflow for hanoi beyond 62 disks in long long.
• -Wunused-parameter on hanoi_moves if you forget to use the via peg.

Runtime symptoms:

• rev returns 0. The base case returns 0 instead of acc — the accumulator's whole point is that it holds the answer.
• rev drops or duplicates a digit. The order inside the call matters: acc*10 + n%10 then n/10. Doing the division first loses the digit.
• Hanoi prints the wrong sequence. The peg rotation is wrong — the auxiliary of one call becomes the destination of the next.
• Program hangs for large n. hanoi_moves genuinely produces 2^n - 1 lines; that is the algorithm, not a bug. Use the counting version to reason about size.
• Leading zeros vanish in rev. Expected — rev(100,0) is 1; numeric reversal cannot preserve them.

Technique: verify hanoi(n) against 2^n - 1 for n up to 20, and trace rev by printing (n, acc) at each level.

Memory safety

• Depth is linear in n, but the work is exponential. hanoi(40) recurses only 40 deep yet performs a trillion conceptual moves — the stack is fine, the runtime is not. Distinguish the two costs.
• Signed overflow. 2 * hanoi(n-1) + 1 overflows int at 31 disks and long long at 63. Bound the input.
• Accumulator overflow. acc*10 + digit can overflow for large inputs; reversing 2147483647 overflows a 32-bit int. Use a wider accumulator or check before multiplying.
• No heap use, so nothing to leak — but hanoi_moves performing exponential I/O can fill a disk or hang a terminal. Guard n before calling it.
• Tail calls are not guaranteed to be optimised, so an accumulator version can still exhaust the stack for very deep recursions.

Real-world uses

Concrete uses: Hanoi itself is mostly pedagogical, but its structure — solve two smaller instances plus one direct step — is exactly the shape of merge sort, quicksort, and many divide-and-conquer algorithms. Accumulators appear throughout functional programming, in parser state threading, in checksum accumulation, and anywhere you want to avoid building a result during unwinding. Backup rotation schemes literally use the Hanoi sequence to schedule tape reuse.

Professional best practices:

Beginner:

• Return the accumulator in the base case.
• Verify the move count formula before trusting a move-printing version.

Intermediate:

• Use accumulators when the natural recursion would otherwise build a large expression on the way back up.
• Do not assume tail-call optimisation in C; measure or convert to a loop when depth is a concern.
• Bound exponential algorithms by input size at the API boundary — the elegance of the code hides the cost.

Practice tasks

1. (Beginner) Count Hanoi moves. Implement long long hanoi(int n). Example: hanoi(3) -> 7; hanoi(10) -> 1023. Concepts: self-similar recurrence.

2. (Beginner) Reverse digits with an accumulator. Implement int rev(int n, int acc). Example: rev(1234, 0) -> 4321. Concepts: carrying state down, base case returns acc.

3. (Intermediate) Print the moves. Implement hanoi_moves and check that it emits exactly 2^n - 1 lines for small n. Concepts: peg rotation, verifying against a formula.

4. (Intermediate) Accumulator vs build-up. Write digit-sum both ways (building on unwind, and with an accumulator) and compare. Concepts: the two recursion styles.

Summary

Hanoi is self-similarity at its clearest — move n-1, move one, move n-1 again — giving 2*moves(n-1) + 1 and therefore 2^n - 1 moves, an exponential cost that is inherent to the problem rather than a flaw in the code. The accumulator pattern introduced alongside it carries the running answer down the recursion so nothing remains to do after the recursive call, which makes the function tail-recursive and shifts the base case to return the accumulator itself. Remember that C does not guarantee tail-call optimisation, and that linear depth can still hide exponential work.

Practice with these exercises

• Tower of Hanoi moves
• Reverse a number