Recursion Examples - Java Programming

Many practical problems involve repeated structure: arrays, strings, mathematical recurrence, and divide-and-conquer search. These examples show common recursive patterns with small, traceable inputs.

Sum of Array

Process one element, then recurse on the rest of the array.

                            ArraySum.java
                        
Replay: real traced execution (multi-file project)

                            import java.util.Arrays;

public class ArraySum {
    public static int sum(int[] arr, int index) {
        if (index >= arr.length) {
            return 0;
        }
        return arr[index] + sum(arr, index + 1);
    }
    public static int sum(int[] arr) {
        return sum(arr, 0);
    }
    public static int sumByLength(int[] arr, int n) {
        if (n <= 0) {
            return 0;
        }
        return arr[n - 1] + sumByLength(arr, n - 1);
    }
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};

        System.out.println("Array: " + Arrays.toString(numbers));
        System.out.println("Sum (index approach): " + sum(numbers));
        System.out.println("Sum (length approach): " + sumByLength(numbers, numbers.length));

        int[] values = {10, 20, 30, 40};
        System.out.println("\nArray: " + Arrays.toString(values));
        System.out.println("Sum: " + sum(values));
    }
}

                        
1public static void main(String[] args)⋯18}19public static void main(String[] args) {20    int[] numbers = {1, 2, 3, 4, 5};2122    System.out.println("Array: " + Arrays.toString(numbers));23    System.out.println("Sum (index approach): " + sum(numbers));24    System.out.println("Sum (length approach): " + sumByLength(numbers, numbers.length));⋯outputArray: [1, 2, 3, 4, 5]
2public static int sum(int[] arr)pass 1 of 2⋯9}10public static int sum(int[] arr) {11    return sum(arr, 0);12}⋯
3public static int sum(int[] arr, int index)pass 1 of 11⋯3public class ArraySum {4    public static int sum(int[] arr, int index0) {5        if (index >= arr.length) {6            return 0;7        }8        return arr[index]1 + sum(arr, index0 + 1);9    }⋯All 11 passes — pass 1 is the card abovepassindexarr[index]arr.length
101—
212—
323—
434—
545—
65—5
7010—
8120—
9230—
10340—
114—4
4if (index >= arr.length)pass 1 of 2⋯4public static int sum(int[] arr, int index) {5    if (index5 >= arr.length5) {6        return 0;7    }⋯
5System.out.println("Sum (index approach): " + sum(numbers));⋯22System.out.println("Array: " + Arrays.toString(numbers));23System.out.println("Sum (index approach): " + sum(numbers));24System.out.println("Sum (length approach): " + sumByLength(numbers, numbers.length5));⋯outputSum (index approach): 15
6public static int sumByLength(int[] arr, int n)pass 1 of 6⋯12}13public static int sumByLength(int[] arr, int n5) {14    if (n <= 0) {15        return 0;16    }17    return arr[n - 1]5 + sumByLength(arr, n5 - 1);18}⋯All 6 passes — pass 1 is the card abovepassnarr[n - 1]
155
244
333
422
511
60—
7if (n <= 0)⋯13public static int sumByLength(int[] arr, int n) {14    if (n0 <= 0) {15        return 0;16    }⋯
8System.out.println("Sum (length approach): " + sumByLength(numbers, nu…⋯23    System.out.println("Sum (index approach): " + sum(numbers));24    System.out.println("Sum (length approach): " + sumByLength(numbers, numbers.length5));2526    int[] values = {10, 20, 30, 40};27    System.out.println("\nArray: " + Arrays.toString(values));28    System.out.println("Sum: " + sum(values));29}⋯outputSum (length approach): 15

Array: [10, 20, 30, 40]
9public static int sum(int[] arr)pass 2 of 2⋯9}10public static int sum(int[] arr) {11    return sum(arr, 0);12}⋯
10if (index >= arr.length)pass 2 of 2⋯4public static int sum(int[] arr, int index) {5    if (index4 >= arr.length4) {6        return 0;7    }⋯
11System.out.println("Sum: " + sum(values));⋯27    System.out.println("\nArray: " + Arrays.toString(values));28    System.out.println("Sum: " + sum(values));29}⋯outputSum: 100

All 11 passes — pass 1 is the card above
pass	`index`	`arr[index]`	`arr.length`
1	0	1	—
2	1	2	—
3	2	3	—
4	3	4	—
5	4	5	—
6	5	—	5
7	0	10	—
8	1	20	—
9	2	30	—
10	3	40	—
11	4	—	4

All 6 passes — pass 1 is the card above
pass	`n`	`arr[n - 1]`
1	5	5
2	4	4
3	3	3
4	2	2
5	1	1
6	0	—

Reverse String

String recursion removes one character at a time until the base case.

                            StringReverse.java
                        
Replay: real traced execution (multi-file project)

                            public class StringReverse {
    public static String reverse(String str) {
        if (str.length() <= 1) {
            return str;
        }
        return str.charAt(str.length() - 1) + reverse(str.substring(0, str.length() - 1));
    }
    public static String reverseAlt(String str) {
        if (str.length() <= 1) {
            return str;
        }
        return reverseAlt(str.substring(1)) + str.charAt(0);
    }
    public static String reverseTrace(String str, int depth) {
        String indent = "  ".repeat(depth);
        System.out.println(indent + "reverse(\"" + str + "\")");

        if (str.length() <= 1) {
            System.out.println(indent + "  → \"" + str + "\"");
            return str;
        }

        char last = str.charAt(str.length() - 1);
        String rest = str.substring(0, str.length() - 1);
        String result = last + reverseTrace(rest, depth + 1);

        System.out.println(indent + "  → \"" + result + "\"");
        return result;
    }
    public static void main(String[] args) {
        String[] words = {"hello", "recursion", "Java"};

        for (String word : words) {
            System.out.println(word + " → " + reverse(word));
        }

        System.out.println("\nAlternative approach:");
        System.out.println("world → " + reverseAlt("world"));

        System.out.println("\nWith trace:");
        reverseTrace("abc", 0);
    }
}

                        
1public static void main(String[] args)⋯29}30public static void main(String[] args) {31    String[] words = {"hello", "recursion", "Java"};⋯
2for (String word : words)pass 1 of 3⋯33for (String wordhello : words) {34    System.out.println(wordhello + " → " + reverse(word));35}⋯All 3 passes — pass 1 is the card abovepassword
1hello
2recursion
3Java
3public static String reverse(String str)pass 1 of 181public class StringReverse {2    public static String reverse(String strhello) {3        if (str.length() <= 1) {4            return str;5        }6        return str.charAt(str.length() - 1) + reverse(str.substring(0, str.length() - 1));7    }⋯18 passes — pass 1 is the card abovepassstr
1hello
2hell
3hel
4he
5h
6recursion
7recursio
8recursi
9recurs
⋯ 7 more passes ⋯
17Ja
18J
4if (str.length() <= 1)pass 1 of 3⋯2public static String reverse(String str) {3    if (str.length() <= 1) {4        return strh;5    }⋯All 3 passes — pass 1 is the card abovepassstr
1h
2r
3J
5System.out.println(word + " → " + reverse(word));⋯33for (String word : words) {34    System.out.println(wordhello + " → " + reverse(word));35}⋯outputhello → olleh
6System.out.println(word + " → " + reverse(word));⋯33for (String word : words) {34    System.out.println(wordrecursion + " → " + reverse(word));35}⋯outputrecursion → noisrucer
7System.out.println(word + " → " + reverse(word));⋯33for (String word : words) {34    System.out.println(wordJava + " → " + reverse(word));35}⋯outputJava → avaJ
8System.out.println(" Alternative approach:");⋯37System.out.println("\nAlternative approach:");38System.out.println("world → " + reverseAlt("world"));⋯output
Alternative approach:
9public static String reverseAlt(String str)pass 1 of 5⋯7}8public static String reverseAlt(String strworld) {9    if (str.length() <= 1) {10        return str;11    }12    return reverseAlt(str.substring(1)) + str.charAt(0);13}⋯All 5 passes — pass 1 is the card abovepassstr
1world
2orld
3rld
4ld
5d
10if (str.length() <= 1)⋯8public static String reverseAlt(String str) {9    if (str.length() <= 1) {10        return strd;11    }⋯
11System.out.println("world → " + reverseAlt("world"));⋯37    System.out.println("\nAlternative approach:");38    System.out.println("world → " + reverseAlt("world"));3940    System.out.println("\nWith trace:");41    reverseTrace("abc", 0);42}⋯outputworld → dlrow

With trace:
12indent ← (empty), last ← c, rest ← abpass 1 of 3⋯13}14public static String reverseTrace(String strabc, int depth0) {15    String indent→ (empty) = "  ".repeat(depth0);16    System.out.println(indent(empty) + "reverse(\"" + strabc + "\")");1718    if (str.length() <= 1) {19        System.out.println(indent + "  → \"" + str + "\"");20        return str;21    }2223    char last→ c = str.charAt(str.length() - 1);24    String rest→ ab = str.substring(0, str.length() - 1);25    String result = lastc + reverseTrace(restab, depth0 + 1);⋯outputreverse("abc")All 3 passes — pass 1 is the card abovepassstrdepthindentlastrest
1abc0(empty)cab
2ab1  ba
3a2    ——
13if (str.length() <= 1)⋯18if (str.length() <= 1) {19    System.out.println(indent     + "  → \"" + stra + "\"");20    return stra;21}⋯output      → "a"
14result ← ba⋯24    String rest = str.substring(0, str.length() - 1);25    String result→ ba = lastb + reverseTrace(resta, depth1 + 1);2627    System.out.println(indent   + "  → \"" + resultba + "\"");28    return resultba;29}⋯output    → "ba"
15result ← cba, last ← c, rest ← ab, depth ← 0⋯24    String rest = str.substring(0, str.length() - 1);25    String result→ cba = last→ c + reverseTrace(rest→ ab, depth→ 0 + 1);2627    System.out.println(indent(empty) + "  → \"" + resultcba + "\"");28    return resultcba;29}⋯output  → "cba"
16reverseTrace("abc", 0);⋯40    System.out.println("\nWith trace:");41    reverseTrace("abc", 0);42}⋯

All 3 passes — pass 1 is the card above
pass	`word`
1	hello
2	recursion
3	Java

18 passes — pass 1 is the card above
pass	`str`
1	hello
2	hell
3	hel
4	he
5	h
6	recursion
7	recursio
8	recursi
9	recurs
⋯ 7 more passes ⋯
17	Ja
18	J

All 3 passes — pass 1 is the card above
pass	`str`
1	h
2	r
3	J

All 5 passes — pass 1 is the card above
pass	`str`
1	world
2	orld
3	rld
4	ld
5	d

All 3 passes — pass 1 is the card above
pass	`str`	`depth`	`indent`	`last`	`rest`
1	abc	0	(empty)	c	ab
2	ab	1		b	a
3	a	2		—	—

Power Function

                            example
                            base = 2, exponent = 5 (default)base = 3exponent = 4
                        

                            Power.java
                        
Replay: real traced execution (multi-file project)

                            public class Power {
    public static int power(int base, int exp) {
        if (exp == 0) {
            return 1;
        }
        return base * power(base, exp - 1);
    }
    public static int powerOptimized(int base, int exp) {
        if (exp == 0) {
            return 1;
        }
        if (exp % 2 == 0) {
            int half = powerOptimized(base, exp / 2);
            return half * half;
        }
        return base * powerOptimized(base, exp - 1);
    }
    private static int callCount = 0;

    public static int powerCounted(int base, int exp) {
        callCount++;
        if (exp == 0) return 1;
        return base * powerCounted(base, exp - 1);
    }

    public static int powerOptimizedCounted(int base, int exp) {
        callCount++;
        if (exp == 0) return 1;
        if (exp % 2 == 0) {
            int half = powerOptimizedCounted(base, exp / 2);
            return half * half;
        }
        return base * powerOptimizedCounted(base, exp - 1);
    }
    public static void main(String[] args) {
        int base = 2;
        int exponent = 5;

        System.out.println(base + "^" + exponent + " = " + power(base, exponent));

        System.out.println("\nOptimized:");
        System.out.println(base + "^" + exponent + " = " + powerOptimized(base, exponent));
        callCount = 0;
        int r1 = powerCounted(base, exponent);
        int calls1 = callCount;

        callCount = 0;
        int r2 = powerOptimizedCounted(base, exponent);
        int calls2 = callCount;

        System.out.println("\nCalls for " + base + "^" + exponent + ":");
        System.out.println("  Simple: " + calls1 + " calls");
        System.out.println("  Optimized: " + calls2 + " calls");
    }
}
public class Power {
    public static int power(int base, int exp) {
        if (exp == 0) {
            return 1;
        }
        return base * power(base, exp - 1);
    }
    public static int powerOptimized(int base, int exp) {
        if (exp == 0) {
            return 1;
        }
        if (exp % 2 == 0) {
            int half = powerOptimized(base, exp / 2);
            return half * half;
        }
        return base * powerOptimized(base, exp - 1);
    }
    private static int callCount = 0;

    public static int powerCounted(int base, int exp) {
        callCount++;
        if (exp == 0) return 1;
        return base * powerCounted(base, exp - 1);
    }

    public static int powerOptimizedCounted(int base, int exp) {
        callCount++;
        if (exp == 0) return 1;
        if (exp % 2 == 0) {
            int half = powerOptimizedCounted(base, exp / 2);
            return half * half;
        }
        return base * powerOptimizedCounted(base, exp - 1);
    }
    public static void main(String[] args) {
        int base = 3;
        int exponent = 5;

        System.out.println(base + "^" + exponent + " = " + power(base, exponent));

        System.out.println("\nOptimized:");
        System.out.println(base + "^" + exponent + " = " + powerOptimized(base, exponent));
        callCount = 0;
        int r1 = powerCounted(base, exponent);
        int calls1 = callCount;

        callCount = 0;
        int r2 = powerOptimizedCounted(base, exponent);
        int calls2 = callCount;

        System.out.println("\nCalls for " + base + "^" + exponent + ":");
        System.out.println("  Simple: " + calls1 + " calls");
        System.out.println("  Optimized: " + calls2 + " calls");
    }
}
public class Power {
    public static int power(int base, int exp) {
        if (exp == 0) {
            return 1;
        }
        return base * power(base, exp - 1);
    }
    public static int powerOptimized(int base, int exp) {
        if (exp == 0) {
            return 1;
        }
        if (exp % 2 == 0) {
            int half = powerOptimized(base, exp / 2);
            return half * half;
        }
        return base * powerOptimized(base, exp - 1);
    }
    private static int callCount = 0;

    public static int powerCounted(int base, int exp) {
        callCount++;
        if (exp == 0) return 1;
        return base * powerCounted(base, exp - 1);
    }

    public static int powerOptimizedCounted(int base, int exp) {
        callCount++;
        if (exp == 0) return 1;
        if (exp % 2 == 0) {
            int half = powerOptimizedCounted(base, exp / 2);
            return half * half;
        }
        return base * powerOptimizedCounted(base, exp - 1);
    }
    public static void main(String[] args) {
        int base = 2;
        int exponent = 4;

        System.out.println(base + "^" + exponent + " = " + power(base, exponent));

        System.out.println("\nOptimized:");
        System.out.println(base + "^" + exponent + " = " + powerOptimized(base, exponent));
        callCount = 0;
        int r1 = powerCounted(base, exponent);
        int calls1 = callCount;

        callCount = 0;
        int r2 = powerOptimizedCounted(base, exponent);
        int calls2 = callCount;

        System.out.println("\nCalls for " + base + "^" + exponent + ":");
        System.out.println("  Simple: " + calls1 + " calls");
        System.out.println("  Optimized: " + calls2 + " calls");
    }
}

                        
1base ← 2, exponent ← 5⋯34}35public static void main(String[] args) {36    int base→ 2 = 2; //@base=2, 337    int exponent→ 5 = 5; //@exponent=5, 43839    System.out.println(base2 + "^" + exponent5 + " = " + power(base, exponent));⋯
2public static int power(int base, int exp)pass 1 of 61public class Power {2    public static int power(int base2, int exp5) {3        if (exp == 0) {4            return 1;5        }6        return base2 * power(base, exp5 - 1);7    }⋯All 6 passes — pass 1 is the card abovepassexp
15
24
33
42
51
60
3if (exp == 0)⋯2public static int power(int base, int exp) {3    if (exp0 == 0) {4        return 1;5    }⋯
4System.out.println(base + "^" + exponent + " = " + power(base, exponen…⋯39System.out.println(base2 + "^" + exponent5 + " = " + power(base, exponent));4041System.out.println("\nOptimized:");42System.out.println(base2 + "^" + exponent5 + " = " + powerOptimized(base, exponent));43callCount = 0;⋯output2^5 = 32

Optimized:
5public static int powerOptimized(int base, int exp)pass 1 of 5⋯7}8public static int powerOptimized(int base2, int exp5) {9    if (exp == 0) {10        return 1;11    }12    if (exp % 2 == 0) {13        int half = powerOptimized(base, exp / 2);14        return half * half;15    }16    return base2 * powerOptimized(base, exp5 - 1);17}⋯All 5 passes — pass 1 is the card abovepassexp
15
24
32
41
50
6if (exp % 2 == 0)pass 1 of 2⋯11}12if (exp4 % 2 == 0) {13    int half = powerOptimized(base2, exp4 / 2);14    return half * half;⋯
7if (exp % 2 == 0)pass 2 of 2⋯11}12if (exp2 % 2 == 0) {13    int half = powerOptimized(base2, exp2 / 2);14    return half * half;⋯
8if (exp == 0)⋯8public static int powerOptimized(int base, int exp) {9    if (exp0 == 0) {10        return 1;11    }⋯
9half ← 2⋯12if (exp % 2 == 0) {13    int half→ 2 = powerOptimized(base2, exp2 / 2);14    return half2 * half;15}⋯
10half ← 4, base ← 2, exp ← 4⋯12if (exp % 2 == 0) {13    int half→ 4 = powerOptimized(base→ 2, exp→ 4 / 2);14    return half4 * half;15}⋯
11callCount ← 0⋯41System.out.println("\nOptimized:");42System.out.println(base2 + "^" + exponent5 + " = " + powerOptimized(base, exponent));43callCount→ 0 = 0;44int r1 = powerCounted(base2, exponent5);45int calls1 = callCount;⋯output2^5 = 32
12callCount ← 1pass 1 of 6⋯20public static int powerCounted(int base2, int exp5) {21    callCount→ 1++;22    if (exp == 0) return 1;23    return base2 * powerCounted(base, exp5 - 1);24}⋯All 6 passes — pass 1 is the card abovepassexpcallCount
150 → 1
241 → 2
332 → 3
423 → 4
514 → 5
605 → 6
13if (exp == 0)⋯21callCount++;22if (exp0 == 0) return 1;23return base * powerCounted(base, exp - 1);⋯
14r1 ← 32, calls1 ← 6, callCount ← 0⋯43callCount = 0;44int r1→ 32 = powerCounted(base2, exponent5);45int calls1→ 6 = callCount;4647callCount→ 0 = 0;48int r2 = powerOptimizedCounted(base2, exponent5);49int calls2 = callCount;⋯
15callCount ← 1pass 1 of 5⋯26public static int powerOptimizedCounted(int base2, int exp5) {27    callCount→ 1++;28    if (exp == 0) return 1;29    if (exp % 2 == 0) {30        int half = powerOptimizedCounted(base, exp / 2);31        return half * half;32    }33    return base2 * powerOptimizedCounted(base, exp5 - 1);34}⋯All 5 passes — pass 1 is the card abovepassexpcallCount
150 → 1
241 → 2
322 → 3
413 → 4
504 → 5
16if (exp % 2 == 0)pass 1 of 2⋯28if (exp == 0) return 1;29if (exp4 % 2 == 0) {30    int half = powerOptimizedCounted(base2, exp4 / 2);31    return half * half;⋯
17if (exp % 2 == 0)pass 2 of 2⋯28if (exp == 0) return 1;29if (exp2 % 2 == 0) {30    int half = powerOptimizedCounted(base2, exp2 / 2);31    return half * half;⋯
18if (exp == 0)⋯27callCount++;28if (exp0 == 0) return 1;29if (exp % 2 == 0) {⋯
19half ← 2⋯29if (exp % 2 == 0) {30    int half→ 2 = powerOptimizedCounted(base2, exp2 / 2);31    return half2 * half;32}⋯
20half ← 4, base ← 2, exp ← 4⋯29if (exp % 2 == 0) {30    int half→ 4 = powerOptimizedCounted(base→ 2, exp→ 4 / 2);31    return half4 * half;32}⋯
21r2 ← 32, calls2 ← 5⋯47    callCount = 0;48    int r2→ 32 = powerOptimizedCounted(base2, exponent5);49    int calls2→ 5 = callCount;5051    System.out.println("\nCalls for " + base2 + "^" + exponent5 + ":");52    System.out.println("  Simple: " + calls16 + " calls");53    System.out.println("  Optimized: " + calls25 + " calls");54}⋯output
Calls for 2^5:
  Simple: 6 calls
  Optimized: 5 calls
1base ← 3, exponent ← 5⋯34}35public static void main(String[] args) {36    int base→ 3 = 3;37    int exponent→ 5 = 5;3839    System.out.println(base3 + "^" + exponent5 + " = " + power(base, exponent));⋯
2public static int power(int base, int exp)pass 1 of 61public class Power {2    public static int power(int base3, int exp5) {3        if (exp == 0) {4            return 1;5        }6        return base3 * power(base, exp5 - 1);7    }⋯All 6 passes — pass 1 is the card abovepassexp
15
24
33
42
51
60
3if (exp == 0)⋯2public static int power(int base, int exp) {3    if (exp0 == 0) {4        return 1;5    }⋯
4System.out.println(base + "^" + exponent + " = " + power(base, exponen…⋯39System.out.println(base3 + "^" + exponent5 + " = " + power(base, exponent));4041System.out.println("\nOptimized:");42System.out.println(base3 + "^" + exponent5 + " = " + powerOptimized(base, exponent));43callCount = 0;⋯output3^5 = 243

Optimized:
5public static int powerOptimized(int base, int exp)pass 1 of 5⋯7}8public static int powerOptimized(int base3, int exp5) {9    if (exp == 0) {10        return 1;11    }12    if (exp % 2 == 0) {13        int half = powerOptimized(base, exp / 2);14        return half * half;15    }16    return base3 * powerOptimized(base, exp5 - 1);17}⋯All 5 passes — pass 1 is the card abovepassexp
15
24
32
41
50
6if (exp % 2 == 0)pass 1 of 2⋯11}12if (exp4 % 2 == 0) {13    int half = powerOptimized(base3, exp4 / 2);14    return half * half;⋯
7if (exp % 2 == 0)pass 2 of 2⋯11}12if (exp2 % 2 == 0) {13    int half = powerOptimized(base3, exp2 / 2);14    return half * half;⋯
8if (exp == 0)⋯8public static int powerOptimized(int base, int exp) {9    if (exp0 == 0) {10        return 1;11    }⋯
9half ← 3⋯12if (exp % 2 == 0) {13    int half→ 3 = powerOptimized(base3, exp2 / 2);14    return half3 * half;15}⋯
10half ← 9, base ← 3, exp ← 4⋯12if (exp % 2 == 0) {13    int half→ 9 = powerOptimized(base→ 3, exp→ 4 / 2);14    return half9 * half;15}⋯
11callCount ← 0⋯41System.out.println("\nOptimized:");42System.out.println(base3 + "^" + exponent5 + " = " + powerOptimized(base, exponent));43callCount→ 0 = 0;44int r1 = powerCounted(base3, exponent5);45int calls1 = callCount;⋯output3^5 = 243
12callCount ← 1pass 1 of 6⋯20public static int powerCounted(int base3, int exp5) {21    callCount→ 1++;22    if (exp == 0) return 1;23    return base3 * powerCounted(base, exp5 - 1);24}⋯All 6 passes — pass 1 is the card abovepassexpcallCount
150 → 1
241 → 2
332 → 3
423 → 4
514 → 5
605 → 6
13if (exp == 0)⋯21callCount++;22if (exp0 == 0) return 1;23return base * powerCounted(base, exp - 1);⋯
14r1 ← 243, calls1 ← 6, callCount ← 0⋯43callCount = 0;44int r1→ 243 = powerCounted(base3, exponent5);45int calls1→ 6 = callCount;4647callCount→ 0 = 0;48int r2 = powerOptimizedCounted(base3, exponent5);49int calls2 = callCount;⋯
15callCount ← 1pass 1 of 5⋯26public static int powerOptimizedCounted(int base3, int exp5) {27    callCount→ 1++;28    if (exp == 0) return 1;29    if (exp % 2 == 0) {30        int half = powerOptimizedCounted(base, exp / 2);31        return half * half;32    }33    return base3 * powerOptimizedCounted(base, exp5 - 1);34}⋯All 5 passes — pass 1 is the card abovepassexpcallCount
150 → 1
241 → 2
322 → 3
413 → 4
504 → 5
16if (exp % 2 == 0)pass 1 of 2⋯28if (exp == 0) return 1;29if (exp4 % 2 == 0) {30    int half = powerOptimizedCounted(base3, exp4 / 2);31    return half * half;⋯
17if (exp % 2 == 0)pass 2 of 2⋯28if (exp == 0) return 1;29if (exp2 % 2 == 0) {30    int half = powerOptimizedCounted(base3, exp2 / 2);31    return half * half;⋯
18if (exp == 0)⋯27callCount++;28if (exp0 == 0) return 1;29if (exp % 2 == 0) {⋯
19half ← 3⋯29if (exp % 2 == 0) {30    int half→ 3 = powerOptimizedCounted(base3, exp2 / 2);31    return half3 * half;32}⋯
20half ← 9, base ← 3, exp ← 4⋯29if (exp % 2 == 0) {30    int half→ 9 = powerOptimizedCounted(base→ 3, exp→ 4 / 2);31    return half9 * half;32}⋯
21r2 ← 243, calls2 ← 5⋯47    callCount = 0;48    int r2→ 243 = powerOptimizedCounted(base3, exponent5);49    int calls2→ 5 = callCount;5051    System.out.println("\nCalls for " + base3 + "^" + exponent5 + ":");52    System.out.println("  Simple: " + calls16 + " calls");53    System.out.println("  Optimized: " + calls25 + " calls");54}⋯output
Calls for 3^5:
  Simple: 6 calls
  Optimized: 5 calls
1base ← 2, exponent ← 4⋯34}35public static void main(String[] args) {36    int base→ 2 = 2;37    int exponent→ 4 = 4;3839    System.out.println(base2 + "^" + exponent4 + " = " + power(base, exponent));⋯
2public static int power(int base, int exp)pass 1 of 51public class Power {2    public static int power(int base2, int exp4) {3        if (exp == 0) {4            return 1;5        }6        return base2 * power(base, exp4 - 1);7    }⋯All 5 passes — pass 1 is the card abovepassexp
14
23
32
41
50
3if (exp == 0)⋯2public static int power(int base, int exp) {3    if (exp0 == 0) {4        return 1;5    }⋯
4System.out.println(base + "^" + exponent + " = " + power(base, exponen…⋯39System.out.println(base2 + "^" + exponent4 + " = " + power(base, exponent));4041System.out.println("\nOptimized:");42System.out.println(base2 + "^" + exponent4 + " = " + powerOptimized(base, exponent));43callCount = 0;⋯output2^4 = 16

Optimized:
5public static int powerOptimized(int base, int exp)pass 1 of 4⋯7}8public static int powerOptimized(int base2, int exp4) {9    if (exp == 0) {⋯All 4 passes — pass 1 is the card abovepassexp
14
22
31
40
6if (exp % 2 == 0)pass 1 of 2⋯11}12if (exp4 % 2 == 0) {13    int half = powerOptimized(base2, exp4 / 2);14    return half * half;⋯
7if (exp % 2 == 0)pass 2 of 2⋯11}12if (exp2 % 2 == 0) {13    int half = powerOptimized(base2, exp2 / 2);14    return half * half;⋯
8if (exp == 0)⋯8public static int powerOptimized(int base, int exp) {9    if (exp0 == 0) {10        return 1;11    }⋯
9half ← 2⋯12if (exp % 2 == 0) {13    int half→ 2 = powerOptimized(base2, exp2 / 2);14    return half2 * half;15}⋯
10half ← 4, base ← 2, exp ← 4⋯12if (exp % 2 == 0) {13    int half→ 4 = powerOptimized(base→ 2, exp→ 4 / 2);14    return half4 * half;15}⋯
11callCount ← 0⋯41System.out.println("\nOptimized:");42System.out.println(base2 + "^" + exponent4 + " = " + powerOptimized(base, exponent));43callCount→ 0 = 0;44int r1 = powerCounted(base2, exponent4);45int calls1 = callCount;⋯output2^4 = 16
12callCount ← 1pass 1 of 5⋯20public static int powerCounted(int base2, int exp4) {21    callCount→ 1++;22    if (exp == 0) return 1;23    return base2 * powerCounted(base, exp4 - 1);24}⋯All 5 passes — pass 1 is the card abovepassexpcallCount
140 → 1
231 → 2
322 → 3
413 → 4
504 → 5
13if (exp == 0)⋯21callCount++;22if (exp0 == 0) return 1;23return base * powerCounted(base, exp - 1);⋯
14r1 ← 16, calls1 ← 5, callCount ← 0⋯43callCount = 0;44int r1→ 16 = powerCounted(base2, exponent4);45int calls1→ 5 = callCount;4647callCount→ 0 = 0;48int r2 = powerOptimizedCounted(base2, exponent4);49int calls2 = callCount;⋯
15callCount ← 1pass 1 of 4⋯26public static int powerOptimizedCounted(int base2, int exp4) {27    callCount→ 1++;28    if (exp == 0) return 1;⋯All 4 passes — pass 1 is the card abovepassexpcallCount
140 → 1
221 → 2
312 → 3
403 → 4
16if (exp % 2 == 0)pass 1 of 2⋯28if (exp == 0) return 1;29if (exp4 % 2 == 0) {30    int half = powerOptimizedCounted(base2, exp4 / 2);31    return half * half;⋯
17if (exp % 2 == 0)pass 2 of 2⋯28if (exp == 0) return 1;29if (exp2 % 2 == 0) {30    int half = powerOptimizedCounted(base2, exp2 / 2);31    return half * half;⋯
18if (exp == 0)⋯27callCount++;28if (exp0 == 0) return 1;29if (exp % 2 == 0) {⋯
19half ← 2⋯29if (exp % 2 == 0) {30    int half→ 2 = powerOptimizedCounted(base2, exp2 / 2);31    return half2 * half;32}⋯
20half ← 4, base ← 2, exp ← 4⋯29if (exp % 2 == 0) {30    int half→ 4 = powerOptimizedCounted(base→ 2, exp→ 4 / 2);31    return half4 * half;32}⋯
21r2 ← 16, calls2 ← 4⋯47    callCount = 0;48    int r2→ 16 = powerOptimizedCounted(base2, exponent4);49    int calls2→ 4 = callCount;5051    System.out.println("\nCalls for " + base2 + "^" + exponent4 + ":");52    System.out.println("  Simple: " + calls15 + " calls");53    System.out.println("  Optimized: " + calls24 + " calls");54}⋯output
Calls for 2^4:
  Simple: 5 calls
  Optimized: 4 calls

All 6 passes — pass 1 is the card above
pass	`exp`
1	5
2	4
3	3
4	2
5	1
6	0

All 5 passes — pass 1 is the card above
pass	`exp`
1	5
2	4
3	2
4	1
5	0

All 6 passes — pass 1 is the card above
pass	`exp`	`callCount`
1	5	0 → 1
2	4	1 → 2
3	3	2 → 3
4	2	3 → 4
5	1	4 → 5
6	0	5 → 6

All 5 passes — pass 1 is the card above
pass	`exp`	`callCount`
1	5	0 → 1
2	4	1 → 2
3	2	2 → 3
4	1	3 → 4
5	0	4 → 5

All 6 passes — pass 1 is the card above
pass	`exp`
1	5
2	4
3	3
4	2
5	1
6	0

All 5 passes — pass 1 is the card above
pass	`exp`
1	5
2	4
3	2
4	1
5	0

All 6 passes — pass 1 is the card above
pass	`exp`	`callCount`
1	5	0 → 1
2	4	1 → 2
3	3	2 → 3
4	2	3 → 4
5	1	4 → 5
6	0	5 → 6

All 5 passes — pass 1 is the card above
pass	`exp`	`callCount`
1	5	0 → 1
2	4	1 → 2
3	2	2 → 3
4	1	3 → 4
5	0	4 → 5

All 5 passes — pass 1 is the card above
pass	`exp`
1	4
2	3
3	2
4	1
5	0

All 4 passes — pass 1 is the card above
pass	`exp`
1	4
2	2
3	1
4	0

All 5 passes — pass 1 is the card above
pass	`exp`	`callCount`
1	4	0 → 1
2	3	1 → 2
3	2	2 → 3
4	1	3 → 4
5	0	4 → 5

All 4 passes — pass 1 is the card above
pass	`exp`	`callCount`
1	4	0 → 1
2	2	1 → 2
3	1	2 → 3
4	0	3 → 4

Efficient Exponentiation Computing x^n by dividing the exponent reduces recursive work from O(n) toward O(log n).

Count Occurrences

Counting combines the current match with the recursive result for the rest.

                            Count.java
                        
Replay: real traced execution (multi-file project)

                            import java.util.Arrays;

public class Count {
    public static int count(int[] arr, int index, int target) {
        if (index >= arr.length) {
            return 0;
        }
        int currentCount = (arr[index] == target) ? 1 : 0;
        return currentCount + count(arr, index + 1, target);
    }
    public static int count(int[] arr, int target) {
        return count(arr, 0, target);
    }
    public static int countChar(String str, char target) {
        if (str.isEmpty()) {
            return 0;
        }
        int currentCount = (str.charAt(0) == target) ? 1 : 0;
        return currentCount + countChar(str.substring(1), target);
    }
    public static int countDigits(int n) {
        if (n < 10) {
            return 1;
        }
        return 1 + countDigits(n / 10);
    }
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 2, 4, 2, 5};

        System.out.println("Array: " + Arrays.toString(numbers));
        System.out.println("Count of 2: " + count(numbers, 2));
        System.out.println("Count of 5: " + count(numbers, 5));
        System.out.println("Count of 9: " + count(numbers, 9));

        String text = "recursion";
        System.out.println("\nString: " + text);
        System.out.println("Count 'r': " + countChar(text, 'r'));
        System.out.println("Count 'i': " + countChar(text, 'i'));

        System.out.println("\nDigits in 12345: " + countDigits(12345));
        System.out.println("Digits in 987: " + countDigits(987));
    }
}

                        
1public static void main(String[] args)⋯26}27public static void main(String[] args) {28    int[] numbers = {1, 2, 3, 2, 4, 2, 5};2930    System.out.println("Array: " + Arrays.toString(numbers));31    System.out.println("Count of 2: " + count(numbers, 2));32    System.out.println("Count of 5: " + count(numbers, 5));⋯outputArray: [1, 2, 3, 2, 4, 2, 5]
2public static int count(int[] arr, int target)pass 1 of 3⋯10}11public static int count(int[] arr, int target2) {12    return count(arr, 0, target2);13}⋯All 3 passes — pass 1 is the card abovepasstarget
12
25
39
3currentCount ← 0pass 1 of 24⋯3public class Count {4    public static int count(int[] arr, int index0, int target2) {5        if (index >= arr.length) {6            return 0;7        }8        int currentCount→ 0 = (arr[index]1 == target2) ? 1 : 0;9        return currentCount0 + count(arr, index0 + 1, target2);10    }⋯24 passes — pass 1 is the card abovepassindextargetarr[index]currentCount
10210
21221
32230
43221
54240
65221
76250
872——
90510
⋯ 13 more passes ⋯
236950
2479——
4if (index >= arr.length)pass 1 of 3⋯4public static int count(int[] arr, int index, int target) {5    if (index7 >= arr.length7) {6        return 0;7    }⋯
5System.out.println("Count of 2: " + count(numbers, 2));⋯30System.out.println("Array: " + Arrays.toString(numbers));31System.out.println("Count of 2: " + count(numbers, 2));32System.out.println("Count of 5: " + count(numbers, 5));33System.out.println("Count of 9: " + count(numbers, 9));⋯outputCount of 2: 3
6System.out.println("Count of 5: " + count(numbers, 5));⋯31System.out.println("Count of 2: " + count(numbers, 2));32System.out.println("Count of 5: " + count(numbers, 5));33System.out.println("Count of 9: " + count(numbers, 9));⋯outputCount of 5: 1
7text ← recursion⋯32System.out.println("Count of 5: " + count(numbers, 5));33System.out.println("Count of 9: " + count(numbers, 9));3435String text→ recursion = "recursion";36System.out.println("\nString: " + textrecursion);37System.out.println("Count 'r': " + countChar(textrecursion, 'r'));38System.out.println("Count 'i': " + countChar(text, 'i'));⋯outputCount of 9: 0

String: recursion
8currentCount ← 1pass 1 of 20⋯13}14public static int countChar(String strrecursion, char targetr) {15    if (str.isEmpty()) {16        return 0;17    }18    int currentCount→ 1 = (str.charAt(0) == targetr) ? 1 : 0;19    return currentCount1 + countChar(str.substring(1), targetr);20}⋯20 passes — pass 1 is the card abovepassstrtargetcurrentCount
1recursionr1
2ecursionr0
3cursionr0
4ursionr0
5rsionr1
6sionr0
7ionr0
8onr0
9nr0
⋯ 9 more passes ⋯
19ni0
20(empty)i—
9System.out.println("Count 'r': " + countChar(text, 'r'));⋯36System.out.println("\nString: " + text);37System.out.println("Count 'r': " + countChar(textrecursion, 'r'));38System.out.println("Count 'i': " + countChar(textrecursion, 'i'));⋯outputCount 'r': 2
10System.out.println("Count 'i': " + countChar(text, 'i'));⋯37System.out.println("Count 'r': " + countChar(text, 'r'));38System.out.println("Count 'i': " + countChar(textrecursion, 'i'));3940System.out.println("\nDigits in 12345: " + countDigits(12345));41System.out.println("Digits in 987: " + countDigits(987));⋯outputCount 'i': 1
11public static int countDigits(int n)pass 1 of 8⋯20}21public static int countDigits(int n12345) {22    if (n < 10) {23        return 1;24    }25    return 1 + countDigits(n12345 / 10);26}⋯All 8 passes — pass 1 is the card abovepassn
112345
21234
3123
412
51
6987
798
89
12if (n < 10)pass 1 of 2⋯21public static int countDigits(int n) {22    if (n1 < 10) {23        return 1;24    }⋯
13System.out.println(" Digits in 12345: " + countDigits(12345));⋯40    System.out.println("\nDigits in 12345: " + countDigits(12345));41    System.out.println("Digits in 987: " + countDigits(987));42}⋯output
Digits in 12345: 5
14if (n < 10)pass 2 of 2⋯21public static int countDigits(int n) {22    if (n9 < 10) {23        return 1;24    }⋯
15System.out.println("Digits in 987: " + countDigits(987));⋯40    System.out.println("\nDigits in 12345: " + countDigits(12345));41    System.out.println("Digits in 987: " + countDigits(987));42}⋯outputDigits in 987: 3

All 3 passes — pass 1 is the card above
pass	`target`
1	2
2	5
3	9

24 passes — pass 1 is the card above
pass	`index`	`target`	`arr[index]`	`currentCount`
1	0	2	1	0
2	1	2	2	1
3	2	2	3	0
4	3	2	2	1
5	4	2	4	0
6	5	2	2	1
7	6	2	5	0
8	7	2	—	—
9	0	5	1	0
⋯ 13 more passes ⋯
23	6	9	5	0
24	7	9	—	—

20 passes — pass 1 is the card above
pass	`str`	`target`	`currentCount`
1	recursion	r	1
2	ecursion	r	0
3	cursion	r	0
4	ursion	r	0
5	rsion	r	1
6	sion	r	0
7	ion	r	0
8	on	r	0
9	n	r	0
⋯ 9 more passes ⋯
19	n	i	0
20	(empty)	i	—

All 8 passes — pass 1 is the card above
pass	`n`
1	12345
2	1234
3	123
4	12
5	1
6	987
7	98
8	9

Recursive Binary Search

Binary search is a divide-and-conquer recursion over a sorted array.

                            target
                            target = 13 (default)target = 8target = 20
                        

                            BinarySearch.java
                        
Replay: real traced execution (multi-file project)

                            import java.util.Arrays;

public class BinarySearch {
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1;
        }
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] > target) {
            return binarySearch(arr, left, mid - 1, target);
        } else {
            return binarySearch(arr, mid + 1, right, target);
        }
    }
    public static int binarySearch(int[] arr, int target) {
        return binarySearch(arr, 0, arr.length - 1, target);
    }
    public static int binarySearchTrace(int[] arr, int left, int right, int target, int depth) {
        String indent = "  ".repeat(depth);

        if (left > right) {
            System.out.println(indent + "Not found");
            return -1;
        }

        int mid = left + (right - left) / 2;
        System.out.println(indent + "Searching [" + left + ".." + right +
                           "], mid=" + mid + " (value=" + arr[mid] + ")");

        if (arr[mid] == target) {
            System.out.println(indent + "Found at index " + mid);
            return mid;
        }

        if (arr[mid] > target) {
            System.out.println(indent + "Go left");
            return binarySearchTrace(arr, left, mid - 1, target, depth + 1);
        } else {
            System.out.println(indent + "Go right");
            return binarySearchTrace(arr, mid + 1, right, target, depth + 1);
        }
    }
    public static void main(String[] args) {
        int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 13;

        System.out.println("Array: " + Arrays.toString(numbers));
        System.out.println("Search 7: index " + binarySearch(numbers, 7));
        System.out.println("Search 15: index " + binarySearch(numbers, 15));
        System.out.println("Search 8: index " + binarySearch(numbers, 8));

        System.out.println("\nSearch " + target + " with trace:");
        binarySearchTrace(numbers, 0, numbers.length - 1, target, 0);
    }
}
import java.util.Arrays;

public class BinarySearch {
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1;
        }
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] > target) {
            return binarySearch(arr, left, mid - 1, target);
        } else {
            return binarySearch(arr, mid + 1, right, target);
        }
    }
    public static int binarySearch(int[] arr, int target) {
        return binarySearch(arr, 0, arr.length - 1, target);
    }
    public static int binarySearchTrace(int[] arr, int left, int right, int target, int depth) {
        String indent = "  ".repeat(depth);

        if (left > right) {
            System.out.println(indent + "Not found");
            return -1;
        }

        int mid = left + (right - left) / 2;
        System.out.println(indent + "Searching [" + left + ".." + right +
                           "], mid=" + mid + " (value=" + arr[mid] + ")");

        if (arr[mid] == target) {
            System.out.println(indent + "Found at index " + mid);
            return mid;
        }

        if (arr[mid] > target) {
            System.out.println(indent + "Go left");
            return binarySearchTrace(arr, left, mid - 1, target, depth + 1);
        } else {
            System.out.println(indent + "Go right");
            return binarySearchTrace(arr, mid + 1, right, target, depth + 1);
        }
    }
    public static void main(String[] args) {
        int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 8;

        System.out.println("Array: " + Arrays.toString(numbers));
        System.out.println("Search 7: index " + binarySearch(numbers, 7));
        System.out.println("Search 15: index " + binarySearch(numbers, 15));
        System.out.println("Search 8: index " + binarySearch(numbers, 8));

        System.out.println("\nSearch " + target + " with trace:");
        binarySearchTrace(numbers, 0, numbers.length - 1, target, 0);
    }
}
import java.util.Arrays;

public class BinarySearch {
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1;
        }
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] > target) {
            return binarySearch(arr, left, mid - 1, target);
        } else {
            return binarySearch(arr, mid + 1, right, target);
        }
    }
    public static int binarySearch(int[] arr, int target) {
        return binarySearch(arr, 0, arr.length - 1, target);
    }
    public static int binarySearchTrace(int[] arr, int left, int right, int target, int depth) {
        String indent = "  ".repeat(depth);

        if (left > right) {
            System.out.println(indent + "Not found");
            return -1;
        }

        int mid = left + (right - left) / 2;
        System.out.println(indent + "Searching [" + left + ".." + right +
                           "], mid=" + mid + " (value=" + arr[mid] + ")");

        if (arr[mid] == target) {
            System.out.println(indent + "Found at index " + mid);
            return mid;
        }

        if (arr[mid] > target) {
            System.out.println(indent + "Go left");
            return binarySearchTrace(arr, left, mid - 1, target, depth + 1);
        } else {
            System.out.println(indent + "Go right");
            return binarySearchTrace(arr, mid + 1, right, target, depth + 1);
        }
    }
    public static void main(String[] args) {
        int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 20;

        System.out.println("Array: " + Arrays.toString(numbers));
        System.out.println("Search 7: index " + binarySearch(numbers, 7));
        System.out.println("Search 15: index " + binarySearch(numbers, 15));
        System.out.println("Search 8: index " + binarySearch(numbers, 8));

        System.out.println("\nSearch " + target + " with trace:");
        binarySearchTrace(numbers, 0, numbers.length - 1, target, 0);
    }
}

                        
1target ← 13⋯45}46public static void main(String[] args) {47    int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};48    int target→ 13 = 13; //@target=13, 8, 204950    System.out.println("Array: " + Arrays.toString(numbers));51    System.out.println("Search 7: index " + binarySearch(numbers, 7));52    System.out.println("Search 15: index " + binarySearch(numbers, 15));⋯outputArray: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
2public static int binarySearch(int[] arr, int target)pass 1 of 3⋯17}18public static int binarySearch(int[] arr, int target7) {19    return binarySearch(arr, 0, arr.length10 - 1, target7);20}⋯All 3 passes — pass 1 is the card abovepasstargetarr[mid]midleftright
17940—
215157——
389403
3mid ← 4pass 1 of 11⋯3public class BinarySearch {4    public static int binarySearch(int[] arr, int left0, int right9, int target7) {5        if (left > right) {6            return -1;7        }8        int mid→ 4 = left0 + (right9 - left) / 2;9        if (arr[mid] == target) {⋯All 11 passes — pass 1 is the card abovepassleftrighttargetarr[mid]mid
109794
2037—1
3237—2
433773
50915—4
65915157
709894
8038—1
9238—2
10338—3
11438——
4if (arr[mid] > target)pass 1 of 2⋯11}12if (arr[mid]9 > target7) {13    return binarySearch(arr, left0, mid4 - 1, target7);14} else {⋯
5elsepass 1 of 6⋯13    return binarySearch(arr, left, mid - 1, target);14} else {15    return binarySearch(arr, mid1 + 1, right3, target7);16}⋯All 6 passes — pass 1 is the card abovepassmidrighttargetarr[mid]left
1137——
22377—
3491515—
4138——
5238——
6338—4
6if (arr[mid] == target)pass 1 of 2⋯8int mid = left + (right - left) / 2;9if (arr[mid]7 == target7) {10    return mid3;11}⋯
7System.out.println("Search 7: index " + binarySearch(numbers, 7));⋯50System.out.println("Array: " + Arrays.toString(numbers));51System.out.println("Search 7: index " + binarySearch(numbers, 7));52System.out.println("Search 15: index " + binarySearch(numbers, 15));53System.out.println("Search 8: index " + binarySearch(numbers, 8));⋯outputSearch 7: index 3
8if (arr[mid] == target)pass 2 of 2⋯8int mid = left + (right - left) / 2;9if (arr[mid]15 == target15) {10    return mid7;11}⋯
9System.out.println("Search 15: index " + binarySearch(numbers, 15));⋯51System.out.println("Search 7: index " + binarySearch(numbers, 7));52System.out.println("Search 15: index " + binarySearch(numbers, 15));53System.out.println("Search 8: index " + binarySearch(numbers, 8));⋯outputSearch 15: index 7
10if (arr[mid] > target)pass 2 of 2⋯11}12if (arr[mid]9 > target8) {13    return binarySearch(arr, left0, mid4 - 1, target8);14} else {⋯
11if (left > right)⋯4public static int binarySearch(int[] arr, int left, int right, int target) {5    if (left4 > right3) {6        return -1;7    }⋯
12System.out.println("Search 8: index " + binarySearch(numbers, 8));⋯52    System.out.println("Search 15: index " + binarySearch(numbers, 15));53    System.out.println("Search 8: index " + binarySearch(numbers, 8));5455    System.out.println("\nSearch " + target13 + " with trace:");56    binarySearchTrace(numbers, 0, numbers.length10 - 1, target13, 0);57}⋯outputSearch 8: index -1

Search 13 with trace:
13indent ← (empty), mid ← 4pass 1 of 4⋯20}21public static int binarySearchTrace(int[] arr, int left0, int right9, int target13, int depth0) {22    String indent→ (empty) = "  ".repeat(depth0);2324    if (left > right) {25        System.out.println(indent + "Not found");26        return -1;27    }2829    int mid→ 4 = left0 + (right9 - left) / 2;30    System.out.println(indent(empty) + "Searching [" + left0 + ".." + right9 + 31                       "], mid=" + mid4 + " (value=" + arr[mid]9 + ")");⋯outputSearching [0..9], mid=4 (value=9)All 4 passes — pass 1 is the card abovepassleftrightdeptharr[mid]indentmid
10909(empty)4
259115  7
356211    5
466313      6
14elsepass 1 of 2⋯40    return binarySearchTrace(arr, left, mid - 1, target, depth + 1);41} else {42    System.out.println(indent(empty) + "Go right");43    return binarySearchTrace(arr, mid4 + 1, right9, target13, depth0 + 1);44}⋯outputGo right
15if (arr[mid] > target)⋯38if (arr[mid]15 > target13) {39    System.out.println(indent   + "Go left");40    return binarySearchTrace(arr, left5, mid7 - 1, target13, depth1 + 1);41} else {⋯output  Go left
16elsepass 2 of 2⋯40    return binarySearchTrace(arr, left, mid - 1, target, depth + 1);41} else {42    System.out.println(indent     + "Go right");43    return binarySearchTrace(arr, mid5 + 1, right6, target13, depth2 + 1);44}⋯output    Go right
17if (arr[mid] == target)⋯33if (arr[mid]13 == target13) {34    System.out.println(indent       + "Found at index " + mid6);35    return mid6;36}⋯output      Found at index 6
18binarySearchTrace(numbers, 0, numbers.length - 1, target, 0);⋯55    System.out.println("\nSearch " + target + " with trace:");56    binarySearchTrace(numbers, 0, numbers.length10 - 1, target13, 0);57}⋯
1target ← 8⋯45}46public static void main(String[] args) {47    int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};48    int target→ 8 = 8;4950    System.out.println("Array: " + Arrays.toString(numbers));51    System.out.println("Search 7: index " + binarySearch(numbers, 7));52    System.out.println("Search 15: index " + binarySearch(numbers, 15));⋯outputArray: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
2public static int binarySearch(int[] arr, int target)pass 1 of 3⋯17}18public static int binarySearch(int[] arr, int target7) {19    return binarySearch(arr, 0, arr.length10 - 1, target7);20}⋯All 3 passes — pass 1 is the card abovepasstargetarr[mid]midleftright
17940—
215157——
389403
3mid ← 4pass 1 of 11⋯3public class BinarySearch {4    public static int binarySearch(int[] arr, int left0, int right9, int target7) {5        if (left > right) {6            return -1;7        }8        int mid→ 4 = left0 + (right9 - left) / 2;9        if (arr[mid] == target) {⋯All 11 passes — pass 1 is the card abovepassleftrighttargetarr[mid]mid
109794
2037—1
3237—2
433773
50915—4
65915157
709894
8038—1
9238—2
10338—3
11438——
4if (arr[mid] > target)pass 1 of 2⋯11}12if (arr[mid]9 > target7) {13    return binarySearch(arr, left0, mid4 - 1, target7);14} else {⋯
5elsepass 1 of 6⋯13    return binarySearch(arr, left, mid - 1, target);14} else {15    return binarySearch(arr, mid1 + 1, right3, target7);16}⋯All 6 passes — pass 1 is the card abovepassmidrighttargetarr[mid]left
1137——
22377—
3491515—
4138——
5238——
6338—4
6if (arr[mid] == target)pass 1 of 2⋯8int mid = left + (right - left) / 2;9if (arr[mid]7 == target7) {10    return mid3;11}⋯
7System.out.println("Search 7: index " + binarySearch(numbers, 7));⋯50System.out.println("Array: " + Arrays.toString(numbers));51System.out.println("Search 7: index " + binarySearch(numbers, 7));52System.out.println("Search 15: index " + binarySearch(numbers, 15));53System.out.println("Search 8: index " + binarySearch(numbers, 8));⋯outputSearch 7: index 3
8if (arr[mid] == target)pass 2 of 2⋯8int mid = left + (right - left) / 2;9if (arr[mid]15 == target15) {10    return mid7;11}⋯
9System.out.println("Search 15: index " + binarySearch(numbers, 15));⋯51System.out.println("Search 7: index " + binarySearch(numbers, 7));52System.out.println("Search 15: index " + binarySearch(numbers, 15));53System.out.println("Search 8: index " + binarySearch(numbers, 8));⋯outputSearch 15: index 7
10if (arr[mid] > target)pass 2 of 2⋯11}12if (arr[mid]9 > target8) {13    return binarySearch(arr, left0, mid4 - 1, target8);14} else {⋯
11if (left > right)⋯4public static int binarySearch(int[] arr, int left, int right, int target) {5    if (left4 > right3) {6        return -1;7    }⋯
12System.out.println("Search 8: index " + binarySearch(numbers, 8));⋯52    System.out.println("Search 15: index " + binarySearch(numbers, 15));53    System.out.println("Search 8: index " + binarySearch(numbers, 8));5455    System.out.println("\nSearch " + target8 + " with trace:");56    binarySearchTrace(numbers, 0, numbers.length10 - 1, target8, 0);57}⋯outputSearch 8: index -1

Search 8 with trace:
13indent ← (empty), mid ← 4pass 1 of 5⋯20}21public static int binarySearchTrace(int[] arr, int left0, int right9, int target8, int depth0) {22    String indent→ (empty) = "  ".repeat(depth0);2324    if (left > right) {25        System.out.println(indent + "Not found");26        return -1;27    }2829    int mid→ 4 = left0 + (right9 - left) / 2;30    System.out.println(indent(empty) + "Searching [" + left0 + ".." + right9 + 31                       "], mid=" + mid4 + " (value=" + arr[mid]9 + ")");⋯outputSearching [0..9], mid=4 (value=9)All 5 passes — pass 1 is the card abovepassleftrightdeptharr[mid]indentmid
10909(empty)4
20313  1
32325    2
43337      3
5434—        —
14if (arr[mid] > target)⋯38if (arr[mid]9 > target8) {39    System.out.println(indent(empty) + "Go left");40    return binarySearchTrace(arr, left0, mid4 - 1, target8, depth0 + 1);41} else {⋯outputGo left
15elsepass 1 of 3⋯40    return binarySearchTrace(arr, left, mid - 1, target, depth + 1);41} else {42    System.out.println(indent   + "Go right");43    return binarySearchTrace(arr, mid1 + 1, right3, target8, depth1 + 1);44}⋯output  Go rightAll 3 passes — pass 1 is the card abovepassindentmiddepthleft
1  11—
2    22—
3      334
16if (left > right)⋯24if (left4 > right3) {25    System.out.println(indent         + "Not found");26    return -1;27}⋯output        Not found
17binarySearchTrace(numbers, 0, numbers.length - 1, target, 0);⋯55    System.out.println("\nSearch " + target + " with trace:");56    binarySearchTrace(numbers, 0, numbers.length10 - 1, target8, 0);57}⋯
1target ← 20⋯45}46public static void main(String[] args) {47    int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};48    int target→ 20 = 20;4950    System.out.println("Array: " + Arrays.toString(numbers));51    System.out.println("Search 7: index " + binarySearch(numbers, 7));52    System.out.println("Search 15: index " + binarySearch(numbers, 15));⋯outputArray: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
2public static int binarySearch(int[] arr, int target)pass 1 of 3⋯17}18public static int binarySearch(int[] arr, int target7) {19    return binarySearch(arr, 0, arr.length10 - 1, target7);20}⋯All 3 passes — pass 1 is the card abovepasstargetarr[mid]midleftright
17940—
215157——
389403
3mid ← 4pass 1 of 11⋯3public class BinarySearch {4    public static int binarySearch(int[] arr, int left0, int right9, int target7) {5        if (left > right) {6            return -1;7        }8        int mid→ 4 = left0 + (right9 - left) / 2;9        if (arr[mid] == target) {⋯All 11 passes — pass 1 is the card abovepassleftrighttargetarr[mid]mid
109794
2037—1
3237—2
433773
50915—4
65915157
709894
8038—1
9238—2
10338—3
11438——
4if (arr[mid] > target)pass 1 of 2⋯11}12if (arr[mid]9 > target7) {13    return binarySearch(arr, left0, mid4 - 1, target7);14} else {⋯
5elsepass 1 of 6⋯13    return binarySearch(arr, left, mid - 1, target);14} else {15    return binarySearch(arr, mid1 + 1, right3, target7);16}⋯All 6 passes — pass 1 is the card abovepassmidrighttargetarr[mid]left
1137——
22377—
3491515—
4138——
5238——
6338—4
6if (arr[mid] == target)pass 1 of 2⋯8int mid = left + (right - left) / 2;9if (arr[mid]7 == target7) {10    return mid3;11}⋯
7System.out.println("Search 7: index " + binarySearch(numbers, 7));⋯50System.out.println("Array: " + Arrays.toString(numbers));51System.out.println("Search 7: index " + binarySearch(numbers, 7));52System.out.println("Search 15: index " + binarySearch(numbers, 15));53System.out.println("Search 8: index " + binarySearch(numbers, 8));⋯outputSearch 7: index 3
8if (arr[mid] == target)pass 2 of 2⋯8int mid = left + (right - left) / 2;9if (arr[mid]15 == target15) {10    return mid7;11}⋯
9System.out.println("Search 15: index " + binarySearch(numbers, 15));⋯51System.out.println("Search 7: index " + binarySearch(numbers, 7));52System.out.println("Search 15: index " + binarySearch(numbers, 15));53System.out.println("Search 8: index " + binarySearch(numbers, 8));⋯outputSearch 15: index 7
10if (arr[mid] > target)pass 2 of 2⋯11}12if (arr[mid]9 > target8) {13    return binarySearch(arr, left0, mid4 - 1, target8);14} else {⋯
11if (left > right)⋯4public static int binarySearch(int[] arr, int left, int right, int target) {5    if (left4 > right3) {6        return -1;7    }⋯
12System.out.println("Search 8: index " + binarySearch(numbers, 8));⋯52    System.out.println("Search 15: index " + binarySearch(numbers, 15));53    System.out.println("Search 8: index " + binarySearch(numbers, 8));5455    System.out.println("\nSearch " + target20 + " with trace:");56    binarySearchTrace(numbers, 0, numbers.length10 - 1, target20, 0);57}⋯outputSearch 8: index -1

Search 20 with trace:
13indent ← (empty), mid ← 4pass 1 of 5⋯20}21public static int binarySearchTrace(int[] arr, int left0, int right9, int target20, int depth0) {22    String indent→ (empty) = "  ".repeat(depth0);2324    if (left > right) {25        System.out.println(indent + "Not found");26        return -1;27    }2829    int mid→ 4 = left0 + (right9 - left) / 2;30    System.out.println(indent(empty) + "Searching [" + left0 + ".." + right9 + 31                       "], mid=" + mid4 + " (value=" + arr[mid]9 + ")");⋯outputSearching [0..9], mid=4 (value=9)All 5 passes — pass 1 is the card abovepassleftdeptharr[mid]indentmid
1009(empty)4
25115  7
38217    8
49319      9
5104—        —
14elsepass 1 of 4⋯40    return binarySearchTrace(arr, left, mid - 1, target, depth + 1);41} else {42    System.out.println(indent(empty) + "Go right");43    return binarySearchTrace(arr, mid4 + 1, right9, target20, depth0 + 1);44}⋯outputGo rightAll 4 passes — pass 1 is the card abovepassindentmiddepthleft
1(empty)40—
2  71—
3    82—
4      9310
15if (left > right)⋯24if (left10 > right9) {25    System.out.println(indent         + "Not found");26    return -1;27}⋯output        Not found
16binarySearchTrace(numbers, 0, numbers.length - 1, target, 0);⋯55    System.out.println("\nSearch " + target + " with trace:");56    binarySearchTrace(numbers, 0, numbers.length10 - 1, target20, 0);57}⋯

All 3 passes — pass 1 is the card above
pass	`target`	`arr[mid]`	`mid`	`left`	`right`
1	7	9	4	0	—
2	15	15	7	—	—
3	8	9	4	0	3

All 11 passes — pass 1 is the card above
pass	`left`	`right`	`target`	`arr[mid]`	`mid`
1	0	9	7	9	4
2	0	3	7	—	1
3	2	3	7	—	2
4	3	3	7	7	3
5	0	9	15	—	4
6	5	9	15	15	7
7	0	9	8	9	4
8	0	3	8	—	1
9	2	3	8	—	2
10	3	3	8	—	3
11	4	3	8	—	—

All 6 passes — pass 1 is the card above
pass	`mid`	`right`	`target`	`arr[mid]`	`left`
1	1	3	7	—	—
2	2	3	7	7	—
3	4	9	15	15	—
4	1	3	8	—	—
5	2	3	8	—	—
6	3	3	8	—	4

All 4 passes — pass 1 is the card above
pass	`left`	`right`	`depth`	`arr[mid]`	`indent`	`mid`
1	0	9	0	9	(empty)	4
2	5	9	1	15		7
3	5	6	2	11		5
4	6	6	3	13		6

All 3 passes — pass 1 is the card above
pass	`target`	`arr[mid]`	`mid`	`left`	`right`
1	7	9	4	0	—
2	15	15	7	—	—
3	8	9	4	0	3

All 11 passes — pass 1 is the card above
pass	`left`	`right`	`target`	`arr[mid]`	`mid`
1	0	9	7	9	4
2	0	3	7	—	1
3	2	3	7	—	2
4	3	3	7	7	3
5	0	9	15	—	4
6	5	9	15	15	7
7	0	9	8	9	4
8	0	3	8	—	1
9	2	3	8	—	2
10	3	3	8	—	3
11	4	3	8	—	—

All 6 passes — pass 1 is the card above
pass	`mid`	`right`	`target`	`arr[mid]`	`left`
1	1	3	7	—	—
2	2	3	7	7	—
3	4	9	15	15	—
4	1	3	8	—	—
5	2	3	8	—	—
6	3	3	8	—	4

All 5 passes — pass 1 is the card above
pass	`left`	`right`	`depth`	`arr[mid]`	`indent`	`mid`
1	0	9	0	9	(empty)	4
2	0	3	1	3		1
3	2	3	2	5		2
4	3	3	3	7		3
5	4	3	4	—		—

All 3 passes — pass 1 is the card above
pass	`mid`	`depth`	`left`
1	1	1	—
2	2	2	—
3	3	3	4

All 3 passes — pass 1 is the card above
pass	`target`	`arr[mid]`	`mid`	`left`	`right`
1	7	9	4	0	—
2	15	15	7	—	—
3	8	9	4	0	3

All 11 passes — pass 1 is the card above
pass	`left`	`right`	`target`	`arr[mid]`	`mid`
1	0	9	7	9	4
2	0	3	7	—	1
3	2	3	7	—	2
4	3	3	7	7	3
5	0	9	15	—	4
6	5	9	15	15	7
7	0	9	8	9	4
8	0	3	8	—	1
9	2	3	8	—	2
10	3	3	8	—	3
11	4	3	8	—	—

All 6 passes — pass 1 is the card above
pass	`mid`	`right`	`target`	`arr[mid]`	`left`
1	1	3	7	—	—
2	2	3	7	7	—
3	4	9	15	15	—
4	1	3	8	—	—
5	2	3	8	—	—
6	3	3	8	—	4

All 5 passes — pass 1 is the card above
pass	`left`	`depth`	`arr[mid]`	`indent`	`mid`
1	0	0	9	(empty)	4
2	5	1	15		7
3	8	2	17		8
4	9	3	19		9
5	10	4	—		—

All 4 passes — pass 1 is the card above
pass	`indent`	`mid`	`depth`	`left`
1	(empty)	4	0	—
2		7	1	—
3		8	2	—
4		9	3	10

GCD

                            Gcd.java
                        
Replay: real traced execution (multi-file project)

                            public class Gcd {
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
    public static int gcdTrace(int a, int b) {
        System.out.println("gcd(" + a + ", " + b + ")");

        if (b == 0) {
            System.out.println("  → " + a);
            return a;
        }

        return gcdTrace(b, a % b);
    }
    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }
    public static int gcdIterative(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    public static void main(String[] args) {
        System.out.println("GCD(48, 18) = " + gcd(48, 18));
        System.out.println("GCD(100, 35) = " + gcd(100, 35));
        System.out.println("GCD(17, 13) = " + gcd(17, 13));

        System.out.println("\nGCD(48, 18) with trace:");
        gcdTrace(48, 18);

        System.out.println("\nLCM(12, 18) = " + lcm(12, 18));
        System.out.println("LCM(7, 5) = " + lcm(7, 5));

        System.out.println("\nIterative GCD(48, 18) = " + gcdIterative(48, 18));
    }
}

                        
1public static void main(String[] args)⋯28}29public static void main(String[] args) {30    System.out.println("GCD(48, 18) = " + gcd(48, 18));31    System.out.println("GCD(100, 35) = " + gcd(100, 35));⋯
2public static int gcd(int a, int b)pass 1 of 201public class Gcd {2    public static int gcd(int a48, int b18) {3        if (b == 0) {4            return a;5        }6        return gcd(b18, a48 % b);7    }⋯20 passes — pass 1 is the card abovepassab
14818
21812
3126
460
510035
63530
7305
850
91713
⋯ 9 more passes ⋯
1921
2010
3if (b == 0)pass 1 of 5⋯2public static int gcd(int a, int b) {3    if (b0 == 0) {4        return a6;5    }⋯All 5 passes — pass 1 is the card abovepassa
16
25
31
46
51
4System.out.println("GCD(48, 18) = " + gcd(48, 18));⋯29public static void main(String[] args) {30    System.out.println("GCD(48, 18) = " + gcd(48, 18));31    System.out.println("GCD(100, 35) = " + gcd(100, 35));32    System.out.println("GCD(17, 13) = " + gcd(17, 13));⋯outputGCD(48, 18) = 6
5System.out.println("GCD(100, 35) = " + gcd(100, 35));⋯30System.out.println("GCD(48, 18) = " + gcd(48, 18));31System.out.println("GCD(100, 35) = " + gcd(100, 35));32System.out.println("GCD(17, 13) = " + gcd(17, 13));⋯outputGCD(100, 35) = 5
6System.out.println("GCD(17, 13) = " + gcd(17, 13));⋯31System.out.println("GCD(100, 35) = " + gcd(100, 35));32System.out.println("GCD(17, 13) = " + gcd(17, 13));3334System.out.println("\nGCD(48, 18) with trace:");35gcdTrace(48, 18);⋯outputGCD(17, 13) = 1

GCD(48, 18) with trace:
7public static int gcdTrace(int a, int b)pass 1 of 4⋯7}8public static int gcdTrace(int a48, int b18) {9    System.out.println("gcd(" + a48 + ", " + b18 + ")");1011    if (b == 0) {12        System.out.println("  → " + a);13        return a;14    }1516    return gcdTrace(b18, a48 % b);17}⋯outputgcd(48, 18)All 4 passes — pass 1 is the card abovepassab
14818
21812
3126
460
8if (b == 0)⋯11if (b0 == 0) {12    System.out.println("  → " + a6);13    return a6;14}⋯output  → 6
9gcdTrace(48, 18);⋯34System.out.println("\nGCD(48, 18) with trace:");35gcdTrace(48, 18);3637System.out.println("\nLCM(12, 18) = " + lcm(12, 18));38System.out.println("LCM(7, 5) = " + lcm(7, 5));⋯
10public static int lcm(int a, int b)pass 1 of 2⋯17}18public static int lcm(int a12, int b18) {19    return (a12 * b18) / gcd(a, b);20}⋯
11System.out.println(" LCM(12, 18) = " + lcm(12, 18));⋯37System.out.println("\nLCM(12, 18) = " + lcm(12, 18));38System.out.println("LCM(7, 5) = " + lcm(7, 5));⋯output
LCM(12, 18) = 36
12public static int lcm(int a, int b)pass 2 of 2⋯17}18public static int lcm(int a7, int b5) {19    return (a7 * b5) / gcd(a, b);20}⋯
13System.out.println("LCM(7, 5) = " + lcm(7, 5));⋯37    System.out.println("\nLCM(12, 18) = " + lcm(12, 18));38    System.out.println("LCM(7, 5) = " + lcm(7, 5));3940    System.out.println("\nIterative GCD(48, 18) = " + gcdIterative(48, 18));41}⋯outputLCM(7, 5) = 35
14public static int gcdIterative(int a, int b)⋯20}21public static int gcdIterative(int a48, int b18) {22    while (b != 0) {⋯
15temp ← 18, b ← 12, a ← 18pass 1 of 3⋯21public static int gcdIterative(int a, int b) {22    while (b18 != 0) {23        int temp→ 18 = b;24        b→ 12 = a48 % b;25        a→ 18 = temp18;26    }⋯All 3 passes — pass 1 is the card abovepasstempba
11818 → 1248 → 18
21212 → 618 → 12
366 → 012 → 6
16return a;⋯26    }27    return a6;28}⋯
17System.out.println(" Iterative GCD(48, 18) = " + gcdIterative(48, 18))…⋯40    System.out.println("\nIterative GCD(48, 18) = " + gcdIterative(48, 18));41}⋯output
Iterative GCD(48, 18) = 6

20 passes — pass 1 is the card above
pass	`a`	`b`
1	48	18
2	18	12
3	12	6
4	6	0
5	100	35
6	35	30
7	30	5
8	5	0
9	17	13
⋯ 9 more passes ⋯
19	2	1
20	1	0

All 5 passes — pass 1 is the card above
pass	`a`
1	6
2	5
3	1
4	6
5	1

All 4 passes — pass 1 is the card above
pass	`a`	`b`
1	48	18
2	18	12
3	12	6
4	6	0

All 3 passes — pass 1 is the card above
pass	`temp`	`b`	`a`
1	18	18 → 12	48 → 18
2	12	12 → 6	18 → 12
3	6	6 → 0	12 → 6

Euclidean Algorithm An efficient method to find the greatest common divisor: GCD(a, b) = GCD(b, a mod b), with base case GCD(a, 0) = a.

Exercise: Practical.java

Implement a recursive method to check if a string is a palindrome

pass	`index`	`arr[index]`	`arr.length`
1	0	1	—
2	1	2	—
3	2	3	—
4	3	4	—
5	4	5	—
6	5	—	5
7	0	10	—
8	1	20	—
9	2	30	—
10	3	40	—
11	4	—	4

pass	`left`	`right`	`target`	`arr[mid]`	`mid`
1	0	9	7	9	4
2	0	3	7	—	1
3	2	3	7	—	2
4	3	3	7	7	3
5	0	9	15	—	4
6	5	9	15	15	7
7	0	9	8	9	4
8	0	3	8	—	1
9	2	3	8	—	2
10	3	3	8	—	3
11	4	3	8	—	—

pass	`left`	`right`	`target`	`arr[mid]`	`mid`
1	0	9	7	9	4
2	0	3	7	—	1
3	2	3	7	—	2
4	3	3	7	7	3
5	0	9	15	—	4
6	5	9	15	15	7
7	0	9	8	9	4
8	0	3	8	—	1
9	2	3	8	—	2
10	3	3	8	—	3
11	4	3	8	—	—

pass	`left`	`right`	`target`	`arr[mid]`	`mid`
1	0	9	7	9	4
2	0	3	7	—	1
3	2	3	7	—	2
4	3	3	7	7	3
5	0	9	15	—	4
6	5	9	15	15	7
7	0	9	8	9	4
8	0	3	8	—	1
9	2	3	8	—	2
10	3	3	8	—	3
11	4	3	8	—	—

pass	`index`	`arr[index]`	`arr.length`
1	0	1	—
2	1	2	—
3	2	3	—
4	3	4	—
5	4	5	—
6	5	—	5
7	0	10	—
8	1	20	—
9	2	30	—
10	3	40	—
11	4	—	4

pass	`left`	`right`	`target`	`arr[mid]`	`mid`
1	0	9	7	9	4
2	0	3	7	—	1
3	2	3	7	—	2
4	3	3	7	7	3
5	0	9	15	—	4
6	5	9	15	15	7
7	0	9	8	9	4
8	0	3	8	—	1
9	2	3	8	—	2
10	3	3	8	—	3
11	4	3	8	—	—

pass	`left`	`right`	`target`	`arr[mid]`	`mid`
1	0	9	7	9	4
2	0	3	7	—	1
3	2	3	7	—	2
4	3	3	7	7	3
5	0	9	15	—	4
6	5	9	15	15	7
7	0	9	8	9	4
8	0	3	8	—	1
9	2	3	8	—	2
10	3	3	8	—	3
11	4	3	8	—	—

pass	`left`	`right`	`target`	`arr[mid]`	`mid`
1	0	9	7	9	4
2	0	3	7	—	1
3	2	3	7	—	2
4	3	3	7	7	3
5	0	9	15	—	4
6	5	9	15	15	7
7	0	9	8	9	4
8	0	3	8	—	1
9	2	3	8	—	2
10	3	3	8	—	3
11	4	3	8	—	—

pass	`index`	`arr[index]`	`arr.length`
1	0	1	—
2	1	2	—
3	2	3	—
4	3	4	—
5	4	5	—
6	5	—	5
7	0	10	—
8	1	20	—
9	2	30	—
10	3	40	—
11	4	—	4

pass	`left`	`right`	`target`	`arr[mid]`	`mid`
1	0	9	7	9	4
2	0	3	7	—	1
3	2	3	7	—	2
4	3	3	7	7	3
5	0	9	15	—	4
6	5	9	15	15	7
7	0	9	8	9	4
8	0	3	8	—	1
9	2	3	8	—	2
10	3	3	8	—	3
11	4	3	8	—	—

pass	`left`	`right`	`target`	`arr[mid]`	`mid`
1	0	9	7	9	4
2	0	3	7	—	1
3	2	3	7	—	2
4	3	3	7	7	3
5	0	9	15	—	4
6	5	9	15	15	7
7	0	9	8	9	4
8	0	3	8	—	1
9	2	3	8	—	2
10	3	3	8	—	3
11	4	3	8	—	—

pass	`left`	`right`	`target`	`arr[mid]`	`mid`
1	0	9	7	9	4
2	0	3	7	—	1
3	2	3	7	—	2
4	3	3	7	7	3
5	0	9	15	—	4
6	5	9	15	15	7
7	0	9	8	9	4
8	0	3	8	—	1
9	2	3	8	—	2
10	3	3	8	—	3
11	4	3	8	—	—