Recursion — ISC Computer Science Topic 3

TOPIC 3A

What is Recursion?

concept · base case · call stack · infinite recursion

Recursion is a programming technique where a method calls itself to solve a problem by breaking it down into smaller sub-problems of the same type, until it reaches a trivially simple case (the base case).

Recursive Case

The general rule — the function calls itself with a smaller/simpler input. Progress toward the base case must be guaranteed.

Base Case ⭐

The simplest input where the answer is known directly — NO recursive call. Without this, recursion never stops (infinite loop / stack overflow).

Return & Combine

Each recursive call returns a value. The caller combines these returned values to build the final answer.

⭐ The Golden Rule of Recursion

Every recursive method MUST have at least one base case. Without a base case, the method will call itself indefinitely, causing a StackOverflowError (infinite recursion). Always identify the base case first before writing any recursive method.

Structure of Every Recursive Method

Java — General Template

returnType recursiveMethod(parameters) {
    // ── STEP 1: Base Case ─────────────────────────────
    if (simplest condition) {
        return known_answer;   // NO recursive call here
    }

    // ── STEP 2: Recursive Case ────────────────────────
    // Reduce problem toward base case
    return combine( recursiveMethod(smaller_input) );
}

The Call Stack — How Recursion Works Internally

Each call to a method pushes a new stack frame onto the call stack. The frame stores local variables and where to return when done. Frames are popped (removed) as each call returns.

CALLING PHASE (frames pushed) →

factorial(4)waiting...

▼

factorial(3)waiting...

▼

factorial(2)waiting...

▼

factorial(1)waiting...

▼

factorial(0)returns 1 🏁

RETURNING PHASE (frames popped) ←

factorial(4)= 4×6 = 24

▲

factorial(3)= 3×2 = 6

▲

factorial(2)= 2×1 = 2

▲

factorial(1)= 1×1 = 1

▲

factorial(0)= 1 (base)

Recursion vs Iteration

Property	Recursion	Iteration
Mechanism	Function calls itself	Loop (for/while)
Termination	Base case	Loop condition
Memory	Stack frame per call (more)	Constant extra memory
Code clarity	Often elegant/compact	Can be more verbose
Best for	Trees, divide-&-conquer, Hanoi	Simple loops, counters
Risk	Stack overflow if no base case	Infinite loop

❌ Infinite Recursion — Never Do This

int bad(int n) {
    return bad(n - 1);  // No base case! → StackOverflowError
}

No base case means the method calls itself forever. Java will throw a StackOverflowError when the call stack runs out of memory.

TOPIC 3B

Factorial

n! = n × (n−1)! — the classic recursion example

Mathematical Definition (Recursive Equation)

Recursive definition of factorial:

0! = 1 ← Base Case

n! = n × (n−1)! ← Recursive Case (for n > 0)

Trace: factorial(4)

  factorial(4)
  = 4 × factorial(3)
        = 3 × factorial(2)
              = 2 × factorial(1)
                    = 1 × factorial(0)
                                = 1          ← BASE CASE returns 1
                    = 1 × 1 = 1              ← factorial(1) returns 1
              = 2 × 1 = 2                    ← factorial(2) returns 2
        = 3 × 2 = 6                          ← factorial(3) returns 6
  = 4 × 6 = 24                              ← factorial(4) returns 24

Java Implementation

Recursive factorial — Java

static long factorial(int n) {
    // Base Case: 0! = 1, 1! = 1
    if (n == 0 || n == 1)
        return 1;

    // Recursive Case: n! = n × (n-1)!
    return n * factorial(n - 1);
}

Base Case(s)

n = 0 → return 1
n = 1 → return 1
(Both are needed since 0! = 1 and 1! = 1)

Recursive Case

n > 1 → return n * factorial(n − 1)
Each call reduces n by 1, guaranteed to reach base case.

Factorial Values Table

n	n!	Recursive call
0	1	Base case
1	1	1 × 0! = 1×1
2	2	2 × 1! = 2×1
3	6	3 × 2! = 3×2
4	24	4 × 3! = 4×6
5	120	5 × 4! = 5×24
6	720	6 × 5! = 6×120
10	3,628,800	10 × 9!

Interactive Factorial Tracer

n =

Click the button to see the recursive trace...

TOPIC 3C

GCD — Euclid's Algorithm

Greatest Common Divisor using the Euclidean method

The GCD (Greatest Common Divisor) of two integers is the largest positive integer that divides both without remainder. Euclid's algorithm computes it elegantly using recursion.

The Euclidean Recursive Equation

gcd(a, 0) = a ← Base Case (when b = 0)

gcd(a, b) = gcd(b, a mod b) ← Recursive Case

Why does this work?

The key insight: any divisor of both a and b also divides (a mod b). So gcd(a, b) = gcd(b, a mod b). Eventually b becomes 0, and gcd(a, 0) = a since a divides itself and divides 0. The value of b strictly decreases with each step (a mod b < b always), guaranteeing termination.

Trace: gcd(48, 18)

  gcd(48, 18)
  → 48 mod 18 = 12  →  gcd(18, 12)
                        → 18 mod 12 = 6   →  gcd(12, 6)
                                              → 12 mod 6 = 0   →  gcd(6, 0)
                                                                    → b=0, return 6  ← BASE CASE
                                              ← return 6
                        ← return 6
  ← return 6

  ∴ GCD(48, 18) = 6 ✓  (verify: 48÷6=8 ✓, 18÷6=3 ✓)

Java Implementation

Recursive GCD — Java (Euclid's Algorithm)

static int gcd(int a, int b) {
    // Base Case: gcd(a, 0) = a
    if (b == 0)
        return a;

    // Recursive Case: gcd(a, b) = gcd(b, a % b)
    return gcd(b, a % b);
}

Interactive GCD Tracer

a = b =

Click the button to see the recursive trace...

TOPIC 3D

Binary Search

Divide and conquer — O(log n) search in sorted array

Binary search finds a target element in a sorted array by repeatedly halving the search space. Each recursive call searches half the remaining elements — making it O(log n).

Algorithm Logic (Recursive Equation)

binarySearch(arr, low, high, key):

if low > high → return -1 ← Base Case: NOT FOUND

mid = (low+high) / 2

if arr[mid] == key → return mid ← Base Case: FOUND

if key < arr[mid] → search left half (low to mid-1)

if key > arr[mid] → search right half (mid+1 to high)

Trace: Search for key=23 in sorted array

Array: [5, 10, 15, 20, 23, 30, 42, 55, 60] (indices 0–8)

Call 1: low=0, high=8, mid=4 → arr[4]=23 → FOUND! return 4 ← BASE CASE

  (Lucky! Found in first call. Let's trace searching for 42:)

Call 1: low=0,  high=8,  mid=4  → arr[4]=23 < 42 → search RIGHT
Call 2: low=5,  high=8,  mid=6  → arr[6]=42 == 42 → FOUND! return 6 ← BASE CASE

  (Now trace for 10:)

Call 1: low=0,  high=8,  mid=4  → arr[4]=23 > 10 → search LEFT
Call 2: low=0,  high=3,  mid=1  → arr[1]=10 == 10 → FOUND! return 1 ← BASE CASE

  (Trace for 99 — not in array:)

Call 1: low=0,  high=8,  mid=4  → arr[4]=23 < 99 → search RIGHT
Call 2: low=5,  high=8,  mid=6  → arr[6]=42 < 99 → search RIGHT
Call 3: low=7,  high=8,  mid=7  → arr[7]=55 < 99 → search RIGHT
Call 4: low=8,  high=8,  mid=8  → arr[8]=60 < 99 → search RIGHT
Call 5: low=9,  high=8  → low > high → return -1 ← BASE CASE (NOT FOUND)

Java Implementation

Recursive Binary Search — Java

static int binarySearch(int[] arr, int low, int high, int key) {
    // Base Case 1: Search space exhausted — not found
    if (low > high)
        return -1;

    int mid = (low + high) / 2;

    // Base Case 2: Key found at mid
    if (arr[mid] == key)
        return mid;

    // Recursive Case 1: Key in left half
    if (key < arr[mid])
        return binarySearch(arr, low, mid - 1, key);

    // Recursive Case 2: Key in right half
    return binarySearch(arr, mid + 1, high, key);
}

// Calling it:
int[] arr = {5, 10, 15, 20, 23, 30, 42, 55, 60};
int pos = binarySearch(arr, 0, arr.length - 1, 42);
// pos = 6

⚠ Prerequisite

Array MUST be sorted in ascending order. Binary search does NOT work on unsorted arrays.

✅ Efficiency

With each call, the search space is halved. So at most ⌈log₂ n⌉ + 1 calls. For n=1000, only ~10 calls!

Interactive Binary Search Tracer

Array (sorted, comma-separated):

Search for key =

Click the button to see the recursive trace...

TOPIC 3E

Base Conversion

Converting decimal → any base using recursion

Recursion provides an elegant way to convert a decimal number to any other base (binary, octal, hexadecimal, etc.). The key insight: digits are extracted in reverse order through repeated division — recursion naturally reverses them!

The Recursive Idea

convert(n, base):

if n == 0 → print nothing ← Base Case

else: convert(n / base, base) ← Print higher digits FIRST

print (n % base) ← Then print this digit

Why recursion is perfect here

When converting decimal to binary, we divide by 2 and collect remainders. But the remainders must be printed in reverse (last remainder = most significant bit). Recursion handles this naturally — it goes deep first (smaller numbers), then prints on the way back up.

Trace: convert(13, 2) → binary

  convert(13, 2):
    13 != 0 → call convert(13/2=6, 2)
      convert(6, 2):
        6 != 0 → call convert(6/2=3, 2)
          convert(3, 2):
            3 != 0 → call convert(3/2=1, 2)
              convert(1, 2):
                1 != 0 → call convert(1/2=0, 2)
                  convert(0, 2):
                    n==0 → BASE CASE: return (print nothing)
                ← back: print 1%2 = 1  → output so far: "1"
              ← back: print 3%2 = 1    → output so far: "11"
            ← back: print 6%2 = 0      → output so far: "110"
          ← back: print 13%2 = 1       → output so far: "1101"

  Result: 13 in binary = 1101 ✓  (verify: 8+4+0+1 = 13 ✓)

Java Implementation

Recursive Base Conversion — Java

static void convertToBase(int n, int base) {
    String digits = "0123456789ABCDEF";  // for hex support

    // Base Case: nothing left to convert
    if (n == 0)
        return;

    // Recursive Call: convert the quotient FIRST (higher digits)
    convertToBase(n / base, base);

    // Print current digit AFTER recursive call (reversal magic!)
    System.out.print(digits.charAt(n % base));
}

// Usage examples:
convertToBase(13,  2);   // → 1101  (binary)
convertToBase(255, 16);  // → FF    (hexadecimal)
convertToBase(64,  8);   // → 100  (octal)

Conversion Examples Table

Decimal	Binary (base 2)	Octal (base 8)	Hex (base 16)
5	101	5	5
10	1010	12	A
13	1101	15	D
16	10000	20	10
25	11001	31	19
255	11111111	377	FF

Interactive Base Conversion Tracer

Decimal = Base =

Click Convert to see the recursive trace...

TOPIC 3F

Tower of Hanoi

The crown jewel of recursion — elegant simplicity over complex iteration

The Tower of Hanoi is the most celebrated example of recursion. A problem that seems impossibly complex has a breathtakingly simple recursive solution — 3 lines of meaningful code!

The Problem

Rules

There are 3 pegs: Source (A), Auxiliary (B), Destination (C)
There are n disks of different sizes stacked on peg A (largest at bottom)
Move ALL disks from peg A to peg C
You can only move ONE disk at a time
You can NEVER place a larger disk on top of a smaller disk

The Recursive Insight

💡 The Elegant Observation

To move n disks from A to C:
1. Move the top (n−1) disks from A to B (using C as auxiliary)
2. Move the largest disk from A to C (just one move!)
3. Move the (n−1) disks from B to C (using A as auxiliary)

This is exact recursion! Steps 1 and 3 are the same problem with n−1 disks. Step 2 is the base case when n=1 (just move the single disk directly).

hanoi(n, source, dest, aux):

if n == 1 → move disk 1 from source to dest ← Base Case

else:

hanoi(n-1, source, aux, dest) ← Move n-1 disks to auxiliary

move disk n from source to dest ← Move largest disk

hanoi(n-1, aux, dest, source) ← Move n-1 disks from aux to dest

Java Implementation

Tower of Hanoi — Java (5 lines!)

static void hanoi(int n, char source, char dest, char aux) {
    // Base Case: only 1 disk — just move it directly
    if (n == 1) {
        System.out.println("Move disk 1 from " + source + " to " + dest);
        return;
    }

    // Step 1: Move top (n-1) disks from source to aux (using dest)
    hanoi(n - 1, source, aux, dest);

    // Step 2: Move the largest disk from source to dest
    System.out.println("Move disk " + n + " from " + source + " to " + dest);

    // Step 3: Move (n-1) disks from aux to dest (using source)
    hanoi(n - 1, aux, dest, source);
}

// Calling it for 3 disks:
hanoi(3, 'A', 'C', 'B');

Trace: hanoi(3, A, C, B)

hanoi(3, A, C, B):
  Step 1: hanoi(2, A, B, C)          ← move top 2 disks A→B
    Step 1a: hanoi(1, A, C, B)
      → Move disk 1 from A to C      [Move 1]
    Step 2a: Move disk 2 from A to B [Move 2]
    Step 3a: hanoi(1, C, B, A)
      → Move disk 1 from C to B      [Move 3]

  Step 2: Move disk 3 from A to C    [Move 4]  ← the largest disk

  Step 3: hanoi(2, B, C, A)          ← move top 2 disks B→C
    Step 1b: hanoi(1, B, A, C)
      → Move disk 1 from B to A      [Move 5]
    Step 2b: Move disk 2 from B to C [Move 6]
    Step 3b: hanoi(1, A, C, B)
      → Move disk 1 from A to C      [Move 7]

Total moves for n=3: 7 moves  (= 2³ - 1 = 7 ✓)

Number of Moves

T(1) = 1 ← Base case: 1 move

T(n) = 2·T(n-1) + 1 ← Recursive case

T(n) = 2ⁿ - 1 ← Closed form solution

n disks	Moves = 2ⁿ − 1	If 1 move/sec
1	1	1 second
2	3	3 seconds
3	7	7 seconds
4	15	15 seconds
10	1,023	~17 minutes
64	18,446,744,073,709,551,615	~585 billion years!

Interactive Tower of Hanoi Visualizer

Disks: Move: 0 / 0

Press Reset then step through the moves...

TOOL

Live Call Tracer

See exactly how any recursion unwinds — step by step

How to Read Recursive Traces

Calling phase: Method calls are made, parameters change, stack grows
Returning phase: Results are computed and returned, stack shrinks
Indentation shows depth — deeper = further down the call stack

All Algorithms — Side by Side Complexity

Algorithm	Base Case(s)	Recursive Case	Time Complexity	Calls for n=5
Factorial	n = 0 or 1	n * fact(n-1)	O(n)	5
GCD(a,b)	b = 0	gcd(b, a%b)	O(log min(a,b))	varies
Binary Search	low>high OR found	search half	O(log n)	~3
Base Conversion	n = 0	conv(n/base)	O(log n)	varies
Tower of Hanoi	n = 1	2 × hanoi(n-1)	O(2ⁿ)	31

PRACTICE

Quick Quiz

ISC exam-style questions on Recursion

Score 0 / 0

Q1. What is the output of: factorial(5)?

5! = 5×4×3×2×1 = 120. Trace: fact(5)=5×fact(4)=5×24=120. fact(4)=4×6=24, fact(3)=3×2=6, fact(2)=2×1=2, fact(1)=1 (base case).

Q2. What is the base case for GCD using Euclid's algorithm?

gcd(a, 0) = a. When b becomes 0, the GCD is a. This is because gcd(a, b) = gcd(b, a%b), and a%0 is undefined — we stop when b=0 and return a.

Q3. How many moves does Tower of Hanoi need for n = 4 disks?

Moves = 2ⁿ - 1 = 2⁴ - 1 = 16 - 1 = 15. For n=1: 1 move. For n=2: 3. For n=3: 7. For n=4: 15.

Q4. What happens if a recursive method has no base case?

Without a base case, the method calls itself indefinitely. Each call adds a new frame to the call stack. When the stack runs out of memory, Java throws a StackOverflowError. Always define a base case!

Q5. In recursive binary search, what are the TWO base cases?

Binary search has two base cases: (1) low > high — search space empty, element not found, return -1. (2) arr[mid] == key — element found, return mid. The recursive cases search the left or right half.

Q6. What is gcd(36, 24) using Euclid's algorithm?

gcd(36,24): 36%24=12 → gcd(24,12): 24%12=0 → gcd(12,0): b=0, return 12. So GCD=12. Verify: 36÷12=3 ✓, 24÷12=2 ✓.

Q7. In recursive base conversion of 13 to binary, in what order are the digits printed?

The recursive call goes deep first (smaller quotients), then prints on the way back. This means the most significant bit (from the deepest call) is printed first. So 13 → 1101 (MSB to LSB). This is the beauty of the recursive approach — it reverses the natural bottom-up order of division.

QUICK REF

Master Cheat Sheet

All recursion patterns — memorise before March 27

Factorial — Base

n==0 || n==1 → return 1

0! = 1, 1! = 1

Factorial — Recursive

return n * factorial(n-1)

n! = n × (n−1)!

GCD — Base

b==0 → return a

gcd(a, 0) = a

GCD — Recursive

return gcd(b, a%b)

Euclid's algorithm

Binary Search — Base 1

low > high → return -1

Not found

Binary Search — Base 2

arr[mid]==key → return mid

Found!

Binary Search — mid

mid = (low + high) / 2

Always integer division

Base Conv — Base

n==0 → return

Nothing left to convert

Base Conv — Recursive

convert(n/base); print(n%base)

Recursive call BEFORE print!

Hanoi — Base

n==1 → move disk 1 directly

Single disk: trivial

Hanoi — Step 1

hanoi(n-1, src, aux, dst)

Move n-1 disks to aux

Hanoi — Step 2

move disk n from src to dst

The largest disk

Hanoi — Step 3

hanoi(n-1, aux, dst, src)

Move n-1 disks from aux

Hanoi — Moves

2ⁿ − 1

Exponential complexity O(2ⁿ)

Stack Overflow

No base case → infinite calls

StackOverflowError in Java

Binary Search

O(log n) time

Array MUST be sorted first

🎯 Top ISC Exam Questions — Recursion

1. Write a recursive method to find the factorial of n. Trace it for n=4.
2. Write a recursive method to find GCD(a, b). Trace gcd(36, 24).
3. Explain the base case and recursive case of binary search.
4. Write a recursive method to convert a decimal number to binary.
5. Write a recursive method for Tower of Hanoi. How many moves for n disks?
6. What is infinite recursion? How can it be avoided?
7. Explain the call stack with reference to a recursive method.
8. Trace binary search on a sorted array for a given key.