Tower of Hanoi: count moves

Challenge

Implement unsigned long long hanoi_moves(int n) that returns the number of single-disk moves required to solve Towers of Hanoi for n disks (0 <= n <= 60).

The classic result: it takes 2^n - 1 moves. You can implement either:

1. Recursively: T(n) = 2 * T(n-1) + 1, T(0) = 0.
2. Closed form: (1ULL << n) - 1ULL.

Either solution is acceptable.

Examples

hanoi_moves(0) -> 0
hanoi_moves(1) -> 1
hanoi_moves(2) -> 3
hanoi_moves(3) -> 7
hanoi_moves(10) -> 1023
hanoi_moves(60) -> 1152921504606846975  // 2^60 - 1

Constraints

• 0 <= n <= 60 (so the answer fits in unsigned long long).
• Either recursion or the closed form is fine.

Edge cases

• n == 0 → 0.
• n == 60 → just below ULLONG_MAX / 16.

Why this matters

Towers of Hanoi is the cleanest demonstration of recursive thinking: to move n disks, first move n-1 to the spare peg, move the largest, then move n-1 back. The closed-form solution (2^n - 1) emerges naturally — a small but real example of how recursion solves exponential problems compactly.

Input format

n in [0, 60].

Output format

2^n - 1 as unsigned long long.

Constraints

Use unsigned long long. Recursive or closed-form both fine.

Starter code

#include <stdint.h>
unsigned long long hanoi_moves(int n) { /* TODO */ return 0; }

Common mistakes

Returning int — overflows at n == 31. Forgetting that recursion past about n == 25 takes noticeable time without memoisation. The closed form is fastest.

Edge cases to handle

n == 0; n == 60; n == 1.

Complexity

Recursive: O(2^n) — but only because the recurrence does 2 calls each level. Closed form: O(1).

Background lessons

• Recursion — base case + smaller subproblem
• Functions

Up next

• Nth Fibonacci
• Factorial