Classic patterns: factorial, Fibonacci, GCD, power, Tower of Hanoi (2ⁿ−1 moves), digit/array recursion

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• How many calls does recursive fib(5) make? from Lesson 2.1.2
• With #define CUBE(x) (x * x * x), what is CUBE(a + 1) for a = 2? from Lesson 1.8
• How many halvings take n down to 1? from Lesson 0.2.1

1 · The Hook

🎣

A temple puzzle: 64 golden disks on a pole, largest at the bottom, to be moved to another pole, one disk at a time, never placing a larger disk on a smaller one, using a third pole as help. The legend says the world ends when the monks finish. Recursion solves it in three lines, and a quick count shows why the world is safe for a while.

2 · Predict First

🤔

Moving n disks in the Tower of Hanoi needs how many moves at least? Try n = 1, 2, 3. Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

1, 3, 7: 2^n^ − 1. For 64 disks that is about 1.8 × 10^19^ moves.

Factorial

n! = n × (n − 1)!, with 0! = 1! = 1. One call per level: n calls, depth n.

long fact(int n)
{
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

int main(void)
{
    printf("%ld %ld\n", fact(5), fact(10));
    return 0;
}

Output

120 3628800

Factorials grow fast: 13! no longer fits in a 32-bit int.

Fibonacci

fib(n) = fib(n − 1) + fib(n − 2), fib(0) = 0, fib(1) = 1. Correct but wasteful: the number of calls grows almost like 2^n^ (Lesson 2.1.2). A loop that keeps the last two values does the same job in n steps.

GCD (Euclid)

The greatest common divisor satisfies gcd(a, b) = gcd(b, a % b) and gcd(a, 0) = a. The second argument shrinks quickly, so very few calls are needed.

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main(void)
{
    printf("%d %d\n", gcd(48, 18), gcd(17, 5));
    return 0;
}

Output

6 1

Trace: gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) → 6.

Power by halving

x^n^ = (x^n/2^)² when n is even, and (x^⌊n/2⌋^)² × x when n is odd. Each call halves n, so only about log₂ n calls are made, instead of n − 1 multiplications:

int mults = 0;

long power(long x, int n)
{
    long half;
    if (n == 0)
        return 1;
    half = power(x, n / 2);
    mults++;
    if (n % 2 == 0)
        return half * half;
    mults++;
    return half * half * x;
}

int main(void)
{
    long v = power(3, 13);
    printf("%ld %d\n", v, mults);
    return 0;
}

Output

1594323 7

3^13^ needs 7 multiplications here instead of 12.

Tower of Hanoi

To move n disks from A to C using B: move the top n − 1 disks from A to B (using C), move the largest disk from A to C, then move the n − 1 disks from B to C (using A). Moves M(n) = 2M(n − 1) + 1, M(0) = 0, so M(n) = 2^n^ − 1.

int moves = 0;

void hanoi(int n, char from, char to, char via)
{
    if (n == 0)
        return;
    hanoi(n - 1, from, via, to);
    moves++;
    printf("disk %d: %c -> %c\n", n, from, to);
    hanoi(n - 1, via, to, from);
}

int main(void)
{
    hanoi(3, 'A', 'C', 'B');
    printf("moves = %d\n", moves);
    return 0;
}

Output

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
moves = 7

Digits and arrays

Numbers shrink by / 10 (drop the last digit, which is % 10). Arrays shrink by looking at one element and recursing on the rest (n − 1 elements, or a + 1):

int maxOf(int a[], int n)
{
    int m;
    if (n == 1)
        return a[0];
    m = maxOf(a, n - 1);
    return a[n - 1] > m ? a[n - 1] : m;
}

int sumOf(int *a, int n)
{
    if (n == 0)
        return 0;
    return *a + sumOf(a + 1, n - 1);
}

int main(void)
{
    int a[] = {7, 3, 19, 4, 11};
    printf("%d %d\n", maxOf(a, 5), sumOf(a, 5));
    return 0;
}

Output

19 44

4 · Visual

Recursion tree of hanoi(3): every box makes one move (pink: the move of its own largest disk; each green box moves disk 1). 7 moves = 2³ − 1.

Tower of Hanoi, n = 3 (A -> C):

   |        |        |              move 1: disk 1 A->C     move 5: disk 1 B->A
  =1=       |        |              move 2: disk 2 A->B     move 6: disk 2 B->C
 ==2==      |        |              move 3: disk 1 C->B     move 7: disk 1 A->C
===3===     |        |              move 4: disk 3 A->C
---A--------B--------C---

 M(n) = 2 M(n-1) + 1 :   M(1)=1, M(2)=3, M(3)=7, M(4)=15, ... M(n) = 2^n - 1

The largest disk moves once; everything above it moves twice as a smaller tower.

5 · Worked Examples

Example 1 Easy

What does this print?

int f(int n)
{
    if (n == 0)
        return 0;
    return (n % 10) + f(n / 10);
}

int main(void)
{
    printf("%d\n", f(98765));
    return 0;
}

Solution

f adds the last digit and recurses on the rest: 5 + 6 + 7 + 8 + 9 = 35.

Output

35

Example 2 Medium

How many recursive calls does gcd(48, 18) make in total (counting the first)?

Solution

gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0): 4 calls.

Example 3 GATE

In the Tower of Hanoi with 5 disks, how many moves are made, and how many times does the largest disk move? How many times does the smallest disk move?

Solution

2⁵ − 1 = 31 moves. The largest disk moves exactly once. The smallest disk moves every other move: 2⁴ = 16 times (in general 2^n−1^).

6 · GATE Traps

⚠️

• Hanoi moves are 2ⁿ − 1, not 2ⁿ; the largest disk moves once, the smallest 2ⁿ⁻¹ times.
• Factorial overflows a 32-bit int beyond 12!.
• Recursive Fibonacci recomputes subproblems: calls grow exponentially.
• gcd(a, 0) = a is the base case; gcd(0, b) works too because gcd(0, b) → gcd(b, 0).
• Power by halving uses about log₂ n calls; check whether a question counts multiplications or calls.

8 · Memory Hook

🧠

“Shrink by one, by half, or by a remainder.” Factorial and arrays shrink by one; power by half; GCD by a remainder; Hanoi by one disk but twice.

9 · Connect the Dots

Lessons 2.1.1–2.1.3 traced and wrote recursive functions. GATE questions often hide extra state inside recursion (a static or global variable) or ask for the value of a strange recursive function for some input. Next lesson answers: how do we compute such values reliably, without tracing every single call?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markHanoi

How many moves does the Tower of Hanoi need for 6 disks?

Numerical answer: ________

Q2MCQ1 markGCD

What does gcd(105, 30) (Euclid’s recursion) return?

• (A) 3
• (B) 5
• (C) 15
• (D) 30

Q3NAT2 marksDigit recursion

What does this print?

int f(int n)
{
    if (n == 0)
        return 0;
    return (n % 10) + f(n / 10);
}

int main(void)
{
    printf("%d\n", f(98765));
    return 0;
}

Numerical answer: ________

Q4MCQ2 marksOutput

What does this print?

int maxOf(int a[], int n)
{
    int m;
    if (n == 1)
        return a[0];
    m = maxOf(a, n - 1);
    return a[n - 1] > m ? a[n - 1] : m;
}

int sumOf(int *a, int n)
{
    if (n == 0)
        return 0;
    return *a + sumOf(a + 1, n - 1);
}

int main(void)
{
    int a[] = {7, 3, 19, 4, 11};
    printf("%d %d\n", maxOf(a, 5), sumOf(a, 5));
    return 0;
}

• (A) 19 33
• (B) 7 44
• (C) 19 44
• (D) 11 44

Q5MSQ2 marksPatterns

Which are true?

• (A) Power by halving computes xⁿ with about log₂ n calls.
• (B) In Hanoi with n disks the smallest disk moves 2ⁿ⁻¹ times.
• (C) Recursive fib(n) makes n calls.
• (D) Recursive factorial(n) makes n calls for n ≥ 1.

11 · Rule Card

• n! = n·(n − 1)!, 0! = 1: n calls.
• fib(n) = fib(n − 1) + fib(n − 2): exponential calls; loop is linear.
• gcd(a, b) = gcd(b, a % b), gcd(a, 0) = a.
• xⁿ by halving: ≈ log₂ n calls.
• Hanoi: M(n) = 2M(n − 1) + 1 = 2ⁿ − 1; largest disk 1 move, smallest 2ⁿ⁻¹.
• Digits: n % 10 last digit, n / 10 rest. Arrays: a[n − 1] + rest, or *a + (a + 1).

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

factorial (recursive)GCD / Euclidpower by halvingTower of Hanoidigit recursionarray recursion

13 · Answer Vault