Recursion Introduction - Java Programming

Recursion lets a method solve a problem by calling itself with a smaller input. It is a natural fit for nested structures, divide-and-conquer algorithms, and mathematical definitions.

Key Components

Base Case The condition where recursion stops, preventing infinite calls.

Recursive Case The part of the method that calls itself with simpler input and moves toward the base case.

Classic Example: Factorial

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

                            public class Factorial {
    public static int factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }
    public static void main(String[] args) {
        for (int i = 0; i <= 6; i++) {
            System.out.println(i + "! = " + factorial(i));
        }

        System.out.println("\n10! = " + factorial(10));
    }
}

                        
1public static void main(String[] args)⋯7}8public static void main(String[] args) {9    for (int i = 0; i <= 6; i++) {⋯
2for (int i = 0; i <= 6; i++)pass 1 of 7⋯8public static void main(String[] args) {9    for (int i0 = 0; i <= 6; i++) {10        System.out.println(i0 + "! = " + factorial(i));11    }⋯All 7 passes — pass 1 is the card abovepassi
10
21
32
43
54
65
76
3public static int factorial(int n)pass 1 of 321public class Factorial {2    public static int factorial(int n0) {3        if (n <= 1) {⋯32 passes — pass 1 is the card abovepassn
10
21
32
41
53
62
71
84
93
⋯ 21 more passes ⋯
312
321
4if (n <= 1)pass 1 of 8⋯2public static int factorial(int n) {3    if (n0 <= 1) {4        return 1;5    }⋯All 8 passes — pass 1 is the card abovepassn
10
21
31
41
51
61
71
81
5System.out.println(i + "! = " + factorial(i));⋯9for (int i = 0; i <= 6; i++) {10    System.out.println(i0 + "! = " + factorial(i));11}⋯output0! = 1
6System.out.println(i + "! = " + factorial(i));⋯9for (int i = 0; i <= 6; i++) {10    System.out.println(i1 + "! = " + factorial(i));11}⋯output1! = 1
7System.out.println(i + "! = " + factorial(i));⋯9for (int i = 0; i <= 6; i++) {10    System.out.println(i2 + "! = " + factorial(i));11}⋯output2! = 2
8System.out.println(i + "! = " + factorial(i));⋯9for (int i = 0; i <= 6; i++) {10    System.out.println(i3 + "! = " + factorial(i));11}⋯output3! = 6
9System.out.println(i + "! = " + factorial(i));⋯9for (int i = 0; i <= 6; i++) {10    System.out.println(i4 + "! = " + factorial(i));11}⋯output4! = 24
10System.out.println(i + "! = " + factorial(i));⋯9for (int i = 0; i <= 6; i++) {10    System.out.println(i5 + "! = " + factorial(i));11}⋯output5! = 120
11System.out.println(i + "! = " + factorial(i));⋯9for (int i = 0; i <= 6; i++) {10    System.out.println(i6 + "! = " + factorial(i));11}⋯output6! = 720
12System.out.println(" 10! = " + factorial(10));⋯13    System.out.println("\n10! = " + factorial(10));14}⋯
13System.out.println(" 10! = " + factorial(10));⋯13    System.out.println("\n10! = " + factorial(10));14}⋯output
10! = 3628800

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

32 passes — pass 1 is the card above
pass	`n`
1	0
2	1
3	2
4	1
5	3
6	2
7	1
8	4
9	3
⋯ 21 more passes ⋯
31	2
32	1

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

Tracing Calls

The call trace shows the stack growing as recursive calls are made and shrinking as results return.

                            n
                            n = 5 (default)n = 0n = 3
                        

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

                            public class Trace {

    private static int depth = 0;
    public static int factorial(int n) {
        String indent = "  ".repeat(depth);

        System.out.println(indent + "→ factorial(" + n + ")");
        depth++;

        int result;
        if (n <= 1) {
            result = 1;
            System.out.println(indent + "  Base case: return 1");
        } else {
            result = n * factorial(n - 1);
            System.out.println(indent + "  Return " + n + " * factorial(" + (n-1) + ") = " + result);
        }

        depth--;
        System.out.println(indent + "← returning " + result);

        return result;
    }
    public static void main(String[] args) {
        int n = 5;

        System.out.println("Computing factorial(" + n + "):\n");
        int result = factorial(n);
        System.out.println("\nFinal result: " + result);
    }
}
public class Trace {

    private static int depth = 0;
    public static int factorial(int n) {
        String indent = "  ".repeat(depth);

        System.out.println(indent + "→ factorial(" + n + ")");
        depth++;

        int result;
        if (n <= 1) {
            result = 1;
            System.out.println(indent + "  Base case: return 1");
        } else {
            result = n * factorial(n - 1);
            System.out.println(indent + "  Return " + n + " * factorial(" + (n-1) + ") = " + result);
        }

        depth--;
        System.out.println(indent + "← returning " + result);

        return result;
    }
    public static void main(String[] args) {
        int n = 0;

        System.out.println("Computing factorial(" + n + "):\n");
        int result = factorial(n);
        System.out.println("\nFinal result: " + result);
    }
}
public class Trace {

    private static int depth = 0;
    public static int factorial(int n) {
        String indent = "  ".repeat(depth);

        System.out.println(indent + "→ factorial(" + n + ")");
        depth++;

        int result;
        if (n <= 1) {
            result = 1;
            System.out.println(indent + "  Base case: return 1");
        } else {
            result = n * factorial(n - 1);
            System.out.println(indent + "  Return " + n + " * factorial(" + (n-1) + ") = " + result);
        }

        depth--;
        System.out.println(indent + "← returning " + result);

        return result;
    }
    public static void main(String[] args) {
        int n = 3;

        System.out.println("Computing factorial(" + n + "):\n");
        int result = factorial(n);
        System.out.println("\nFinal result: " + result);
    }
}

                        
1n ← 5⋯23}24public static void main(String[] args) {25    int n→ 5 = 5; //@n=5, 3, 02627    System.out.println("Computing factorial(" + n5 + "):\n");28    int result = factorial(n5);29    System.out.println("\nFinal result: " + result);⋯outputComputing factorial(5):
2indent ← (empty), depth ← 1pass 1 of 5⋯3private static int depth = 0;4public static int factorial(int n5) {5    String indent→ (empty) = "  ".repeat(depth0);67    System.out.println(indent(empty) + "→ factorial(" + n5 + ")");8    depth→ 1++;910    int result;11    if (n <= 1) {⋯output→ factorial(5)All 5 passes — pass 1 is the card abovepassnindentdepthresult
15(empty)0 → 1—
24  1 → 2—
33    2 → 3—
42      3 → 4—
51        4 → 51
3elsepass 1 of 4⋯13    System.out.println(indent + "  Base case: return 1");14} else {15    result = n5 * factorial(n - 1);16    System.out.println(indent + "  Return " + n + " * factorial(" + (n-1) + ") = " + result);⋯All 4 passes — pass 1 is the card abovepassnindentresult
15——
24——
33——
42        1
4result ← 1⋯10int result;11if (n1 <= 1) {12    result→ 1 = 1;13    System.out.println(indent         + "  Base case: return 1");14} else {⋯output          Base case: return 1
5depth ← 4⋯19    depth→ 4--;20    System.out.println(indent         + "← returning " + result1);2122    return result1;23}⋯output        ← returning 1
6result ← 2⋯14} else {15    result→ 2 = n2 * factorial(n - 1);16    System.out.println(indent       + "  Return " + n2 + " * factorial(" + (n-1) + ") = " + result2);17}⋯output        Return 2 * factorial(1) = 2
7depth ← 3⋯19    depth→ 3--;20    System.out.println(indent       + "← returning " + result2);2122    return result2;23}⋯output      ← returning 2
8result ← 6, n ← 3⋯14} else {15    result→ 6 = n→ 3 * factorial(n - 1);16    System.out.println(indent     + "  Return " + n3 + " * factorial(" + (n-1) + ") = " + result6);17}⋯output      Return 3 * factorial(2) = 6
9depth ← 2⋯19    depth→ 2--;20    System.out.println(indent     + "← returning " + result6);2122    return result6;23}⋯output    ← returning 6
10result ← 24, n ← 4⋯14} else {15    result→ 24 = n→ 4 * factorial(n - 1);16    System.out.println(indent   + "  Return " + n4 + " * factorial(" + (n-1) + ") = " + result24);17}⋯output    Return 4 * factorial(3) = 24
11depth ← 1⋯19    depth→ 1--;20    System.out.println(indent   + "← returning " + result24);2122    return result24;23}⋯output  ← returning 24
12result ← 120, n ← 5⋯14} else {15    result→ 120 = n→ 5 * factorial(n - 1);16    System.out.println(indent(empty) + "  Return " + n5 + " * factorial(" + (n-1) + ") = " + result120);17}⋯output  Return 5 * factorial(4) = 120
13depth ← 0⋯19    depth→ 0--;20    System.out.println(indent(empty) + "← returning " + result120);2122    return result120;23}⋯output← returning 120
14result ← 120⋯27    System.out.println("Computing factorial(" + n + "):\n");28    int result→ 120 = factorial(n5);29    System.out.println("\nFinal result: " + result120);30}⋯output
Final result: 120
1n ← 0⋯23}24public static void main(String[] args) {25    int n→ 0 = 0;2627    System.out.println("Computing factorial(" + n0 + "):\n");28    int result = factorial(n0);29    System.out.println("\nFinal result: " + result);⋯outputComputing factorial(0):
2indent ← (empty), depth ← 1⋯3private static int depth = 0;4public static int factorial(int n0) {5    String indent→ (empty) = "  ".repeat(depth0);67    System.out.println(indent(empty) + "→ factorial(" + n0 + ")");8    depth→ 1++;910    int result;11    if (n <= 1) {⋯output→ factorial(0)
3result ← 1⋯10int result;11if (n0 <= 1) {12    result→ 1 = 1;13    System.out.println(indent(empty) + "  Base case: return 1");14} else {⋯output  Base case: return 1
4depth ← 0⋯19    depth→ 0--;20    System.out.println(indent(empty) + "← returning " + result1);2122    return result1;23}⋯output← returning 1
5result ← 1⋯27    System.out.println("Computing factorial(" + n + "):\n");28    int result→ 1 = factorial(n0);29    System.out.println("\nFinal result: " + result1);30}⋯output
Final result: 1
1n ← 3⋯23}24public static void main(String[] args) {25    int n→ 3 = 3;2627    System.out.println("Computing factorial(" + n3 + "):\n");28    int result = factorial(n3);29    System.out.println("\nFinal result: " + result);⋯outputComputing factorial(3):
2indent ← (empty), depth ← 1pass 1 of 3⋯3private static int depth = 0;4public static int factorial(int n3) {5    String indent→ (empty) = "  ".repeat(depth0);67    System.out.println(indent(empty) + "→ factorial(" + n3 + ")");8    depth→ 1++;910    int result;11    if (n <= 1) {⋯output→ factorial(3)All 3 passes — pass 1 is the card abovepassnindentdepthresult
13(empty)0 → 1—
22  1 → 2—
31    2 → 31
3elsepass 1 of 2⋯13    System.out.println(indent + "  Base case: return 1");14} else {15    result = n3 * factorial(n - 1);16    System.out.println(indent + "  Return " + n + " * factorial(" + (n-1) + ") = " + result);⋯
4elsepass 2 of 2⋯13    System.out.println(indent + "  Base case: return 1");14} else {15    result = n2 * factorial(n - 1);16    System.out.println(indent + "  Return " + n + " * factorial(" + (n-1) + ") = " + result);⋯
5result ← 1⋯10int result;11if (n1 <= 1) {12    result→ 1 = 1;13    System.out.println(indent     + "  Base case: return 1");14} else {⋯output      Base case: return 1
6depth ← 2⋯19    depth→ 2--;20    System.out.println(indent     + "← returning " + result1);2122    return result1;23}⋯output    ← returning 1
7result ← 2⋯14} else {15    result→ 2 = n2 * factorial(n - 1);16    System.out.println(indent   + "  Return " + n2 + " * factorial(" + (n-1) + ") = " + result2);17}⋯output    Return 2 * factorial(1) = 2
8depth ← 1⋯19    depth→ 1--;20    System.out.println(indent   + "← returning " + result2);2122    return result2;23}⋯output  ← returning 2
9result ← 6, n ← 3⋯14} else {15    result→ 6 = n→ 3 * factorial(n - 1);16    System.out.println(indent(empty) + "  Return " + n3 + " * factorial(" + (n-1) + ") = " + result6);17}⋯output  Return 3 * factorial(2) = 6
10depth ← 0⋯19    depth→ 0--;20    System.out.println(indent(empty) + "← returning " + result6);2122    return result6;23}⋯output← returning 6
11result ← 6⋯27    System.out.println("Computing factorial(" + n + "):\n");28    int result→ 6 = factorial(n3);29    System.out.println("\nFinal result: " + result6);30}⋯output
Final result: 6

All 5 passes — pass 1 is the card above
pass	`n`	`indent`	`depth`	`result`
1	5	(empty)	0 → 1	—
2	4		1 → 2	—
3	3		2 → 3	—
4	2		3 → 4	—
5	1		4 → 5	1

All 4 passes — pass 1 is the card above
pass	`n`	`indent`	`result`
1	5	—	—
2	4	—	—
3	3	—	—
4	2		1

All 3 passes — pass 1 is the card above
pass	`n`	`indent`	`depth`	`result`
1	3	(empty)	0 → 1	—
2	2		1 → 2	—
3	1		2 → 3	1

Call Stack A memory structure that tracks active method calls. Recursive calls add stack frames until base cases return.

Recursion and Iteration

Some recursive algorithms can also be written as loops. Comparing both versions helps clarify the tradeoff.

                            n
                            n = 20 (default)n = 10
                        

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

                            public class VsIteration {
    public static int sumRecursive(int n) {
        if (n <= 0) {
            return 0;
        }
        return n + sumRecursive(n - 1);
    }
    public static int sumIterative(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += i;
        }
        return sum;
    }
    public static int powerRecursive(int base, int exp) {
        if (exp == 0) {
            return 1;
        }
        return base * powerRecursive(base, exp - 1);
    }
    public static int powerIterative(int base, int exp) {
        int result = 1;
        for (int i = 0; i < exp; i++) {
            result *= base;
        }
        return result;
    }
    public static void main(String[] args) {
        System.out.println("Sum 1 to 10:");
        System.out.println("  Recursive: " + sumRecursive(10));
        System.out.println("  Iterative: " + sumIterative(10));

        System.out.println("\n2^8:");
        System.out.println("  Recursive: " + powerRecursive(2, 8));
        System.out.println("  Iterative: " + powerIterative(2, 8));
        int n = 20;
        int r1 = sumRecursive(n);
        int r2 = sumIterative(n);

        System.out.println("\nWork comparison (sum to " + n + "):");
        System.out.println("  Recursive result: " + r1);
        System.out.println("  Iterative result: " + r2);
        System.out.println("  Both do " + n + " additions");
    }
}
public class VsIteration {
    public static int sumRecursive(int n) {
        if (n <= 0) {
            return 0;
        }
        return n + sumRecursive(n - 1);
    }
    public static int sumIterative(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += i;
        }
        return sum;
    }
    public static int powerRecursive(int base, int exp) {
        if (exp == 0) {
            return 1;
        }
        return base * powerRecursive(base, exp - 1);
    }
    public static int powerIterative(int base, int exp) {
        int result = 1;
        for (int i = 0; i < exp; i++) {
            result *= base;
        }
        return result;
    }
    public static void main(String[] args) {
        System.out.println("Sum 1 to 10:");
        System.out.println("  Recursive: " + sumRecursive(10));
        System.out.println("  Iterative: " + sumIterative(10));

        System.out.println("\n2^8:");
        System.out.println("  Recursive: " + powerRecursive(2, 8));
        System.out.println("  Iterative: " + powerIterative(2, 8));
        int n = 10;
        int r1 = sumRecursive(n);
        int r2 = sumIterative(n);

        System.out.println("\nWork comparison (sum to " + n + "):");
        System.out.println("  Recursive result: " + r1);
        System.out.println("  Iterative result: " + r2);
        System.out.println("  Both do " + n + " additions");
    }
}

                        
1public static void main(String[] args)⋯27}28public static void main(String[] args) {29    System.out.println("Sum 1 to 10:");30    System.out.println("  Recursive: " + sumRecursive(10));31    System.out.println("  Iterative: " + sumIterative(10));⋯outputSum 1 to 10:
2public static int sumRecursive(int n)pass 1 of 321public class VsIteration {2    public static int sumRecursive(int n10) {3        if (n <= 0) {4            return 0;5        }6        return n10 + sumRecursive(n - 1);7    }⋯32 passes — pass 1 is the card abovepassn
110
29
38
47
56
65
74
83
92
⋯ 21 more passes ⋯
311
320
3if (n <= 0)pass 1 of 2⋯2public static int sumRecursive(int n) {3    if (n0 <= 0) {4        return 0;5    }⋯
4System.out.println("  Recursive: " + sumRecursive(10));⋯29System.out.println("Sum 1 to 10:");30System.out.println("  Recursive: " + sumRecursive(10));31System.out.println("  Iterative: " + sumIterative(10));⋯output  Recursive: 55
5sum ← 0pass 1 of 2⋯7}8public static int sumIterative(int n10) {9    int sum→ 0 = 0;10    for (int i = 1; i <= n; i++) {⋯
6sum ← 1pass 1 of 30⋯9int sum = 0;10for (int i1 = 1; i <= n10; i++) {11    sum→ 1 += i1;12}⋯30 passes — pass 1 is the card abovepassinsum
11100 → 1
22101 → 3
33103 → 6
44106 → 10
551010 → 15
661015 → 21
771021 → 28
881028 → 36
991036 → 45
⋯ 19 more passes ⋯
291920171 → 190
302020190 → 210
7return sum;⋯12    }13    return sum55;14}⋯
8System.out.println("  Iterative: " + sumIterative(10));⋯30System.out.println("  Recursive: " + sumRecursive(10));31System.out.println("  Iterative: " + sumIterative(10));3233System.out.println("\n2^8:");34System.out.println("  Recursive: " + powerRecursive(2, 8));35System.out.println("  Iterative: " + powerIterative(2, 8));⋯output  Iterative: 55

2^8:
9public static int powerRecursive(int base, int exp)pass 1 of 9⋯14}15public static int powerRecursive(int base2, int exp8) {16    if (exp == 0) {17        return 1;18    }19    return base2 * powerRecursive(base, exp8 - 1);20}⋯All 9 passes — pass 1 is the card abovepassexp
18
27
36
45
54
63
72
81
90
10if (exp == 0)⋯15public static int powerRecursive(int base, int exp) {16    if (exp0 == 0) {17        return 1;18    }⋯
11System.out.println("  Recursive: " + powerRecursive(2, 8));⋯33System.out.println("\n2^8:");34System.out.println("  Recursive: " + powerRecursive(2, 8));35System.out.println("  Iterative: " + powerIterative(2, 8));36int n = 20; //@n=10, 20⋯output  Recursive: 256
12result ← 1⋯20}21public static int powerIterative(int base2, int exp8) {22    int result→ 1 = 1;23    for (int i = 0; i < exp; i++) {⋯
13result ← 2pass 1 of 8⋯22int result = 1;23for (int i0 = 0; i < exp8; i++) {24    result→ 2 *= base2;25}⋯All 8 passes — pass 1 is the card abovepassiresult
101 → 2
212 → 4
324 → 8
438 → 16
5416 → 32
6532 → 64
7664 → 128
87128 → 256
14return result;⋯25    }26    return result256;27}⋯
15n ← 20⋯34System.out.println("  Recursive: " + powerRecursive(2, 8));35System.out.println("  Iterative: " + powerIterative(2, 8));36int n→ 20 = 20; //@n=10, 2037int r1 = sumRecursive(n20);38int r2 = sumIterative(n);⋯output  Iterative: 256
16if (n <= 0)pass 2 of 2⋯2public static int sumRecursive(int n) {3    if (n0 <= 0) {4        return 0;5    }⋯
17r1 ← 210⋯36int n = 20; //@n=10, 2037int r1→ 210 = sumRecursive(n20);38int r2 = sumIterative(n20);⋯
18sum ← 0pass 2 of 2⋯7}8public static int sumIterative(int n20) {9    int sum→ 0 = 0;10    for (int i = 1; i <= n; i++) {⋯
19return sum;⋯12    }13    return sum210;14}⋯
20r2 ← 210⋯37    int r1 = sumRecursive(n);38    int r2→ 210 = sumIterative(n20);3940    System.out.println("\nWork comparison (sum to " + n20 + "):");41    System.out.println("  Recursive result: " + r1210);42    System.out.println("  Iterative result: " + r2210);43    System.out.println("  Both do " + n20 + " additions");44}⋯output
Work comparison (sum to 20):
  Recursive result: 210
  Iterative result: 210
  Both do 20 additions
1public static void main(String[] args)⋯27}28public static void main(String[] args) {29    System.out.println("Sum 1 to 10:");30    System.out.println("  Recursive: " + sumRecursive(10));31    System.out.println("  Iterative: " + sumIterative(10));⋯outputSum 1 to 10:
2public static int sumRecursive(int n)pass 1 of 221public class VsIteration {2    public static int sumRecursive(int n10) {3        if (n <= 0) {4            return 0;5        }6        return n10 + sumRecursive(n - 1);7    }⋯22 passes — pass 1 is the card abovepassn
110
29
38
47
56
65
74
83
92
⋯ 11 more passes ⋯
211
220
3if (n <= 0)pass 1 of 2⋯2public static int sumRecursive(int n) {3    if (n0 <= 0) {4        return 0;5    }⋯
4System.out.println("  Recursive: " + sumRecursive(10));⋯29System.out.println("Sum 1 to 10:");30System.out.println("  Recursive: " + sumRecursive(10));31System.out.println("  Iterative: " + sumIterative(10));⋯output  Recursive: 55
5sum ← 0pass 1 of 2⋯7}8public static int sumIterative(int n10) {9    int sum→ 0 = 0;10    for (int i = 1; i <= n; i++) {⋯
6sum ← 1pass 1 of 20⋯9int sum = 0;10for (int i1 = 1; i <= n10; i++) {11    sum→ 1 += i1;12}⋯20 passes — pass 1 is the card abovepassisum
110 → 1
221 → 3
333 → 6
446 → 10
5510 → 15
6615 → 21
7721 → 28
8828 → 36
9936 → 45
⋯ 9 more passes ⋯
19936 → 45
201045 → 55
7return sum;⋯12    }13    return sum55;14}⋯
8System.out.println("  Iterative: " + sumIterative(10));⋯30System.out.println("  Recursive: " + sumRecursive(10));31System.out.println("  Iterative: " + sumIterative(10));3233System.out.println("\n2^8:");34System.out.println("  Recursive: " + powerRecursive(2, 8));35System.out.println("  Iterative: " + powerIterative(2, 8));⋯output  Iterative: 55

2^8:
9public static int powerRecursive(int base, int exp)pass 1 of 9⋯14}15public static int powerRecursive(int base2, int exp8) {16    if (exp == 0) {17        return 1;18    }19    return base2 * powerRecursive(base, exp8 - 1);20}⋯All 9 passes — pass 1 is the card abovepassexp
18
27
36
45
54
63
72
81
90
10if (exp == 0)⋯15public static int powerRecursive(int base, int exp) {16    if (exp0 == 0) {17        return 1;18    }⋯
11System.out.println("  Recursive: " + powerRecursive(2, 8));⋯33System.out.println("\n2^8:");34System.out.println("  Recursive: " + powerRecursive(2, 8));35System.out.println("  Iterative: " + powerIterative(2, 8));36int n = 10;⋯output  Recursive: 256
12result ← 1⋯20}21public static int powerIterative(int base2, int exp8) {22    int result→ 1 = 1;23    for (int i = 0; i < exp; i++) {⋯
13result ← 2pass 1 of 8⋯22int result = 1;23for (int i0 = 0; i < exp8; i++) {24    result→ 2 *= base2;25}⋯All 8 passes — pass 1 is the card abovepassiresult
101 → 2
212 → 4
324 → 8
438 → 16
5416 → 32
6532 → 64
7664 → 128
87128 → 256
14return result;⋯25    }26    return result256;27}⋯
15n ← 10⋯34System.out.println("  Recursive: " + powerRecursive(2, 8));35System.out.println("  Iterative: " + powerIterative(2, 8));36int n→ 10 = 10;37int r1 = sumRecursive(n10);38int r2 = sumIterative(n);⋯output  Iterative: 256
16if (n <= 0)pass 2 of 2⋯2public static int sumRecursive(int n) {3    if (n0 <= 0) {4        return 0;5    }⋯
17r1 ← 55⋯36int n = 10;37int r1→ 55 = sumRecursive(n10);38int r2 = sumIterative(n10);⋯
18sum ← 0pass 2 of 2⋯7}8public static int sumIterative(int n10) {9    int sum→ 0 = 0;10    for (int i = 1; i <= n; i++) {⋯
19return sum;⋯12    }13    return sum55;14}⋯
20r2 ← 55⋯37    int r1 = sumRecursive(n);38    int r2→ 55 = sumIterative(n10);3940    System.out.println("\nWork comparison (sum to " + n10 + "):");41    System.out.println("  Recursive result: " + r155);42    System.out.println("  Iterative result: " + r255);43    System.out.println("  Both do " + n10 + " additions");44}⋯output
Work comparison (sum to 10):
  Recursive result: 55
  Iterative result: 55
  Both do 10 additions

32 passes — pass 1 is the card above
pass	`n`
1	10
2	9
3	8
4	7
5	6
6	5
7	4
8	3
9	2
⋯ 21 more passes ⋯
31	1
32	0

30 passes — pass 1 is the card above
pass	`i`	`n`	`sum`
1	1	10	0 → 1
2	2	10	1 → 3
3	3	10	3 → 6
4	4	10	6 → 10
5	5	10	10 → 15
6	6	10	15 → 21
7	7	10	21 → 28
8	8	10	28 → 36
9	9	10	36 → 45
⋯ 19 more passes ⋯
29	19	20	171 → 190
30	20	20	190 → 210

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

All 8 passes — pass 1 is the card above
pass	`i`	`result`
1	0	1 → 2
2	1	2 → 4
3	2	4 → 8
4	3	8 → 16
5	4	16 → 32
6	5	32 → 64
7	6	64 → 128
8	7	128 → 256

22 passes — pass 1 is the card above
pass	`n`
1	10
2	9
3	8
4	7
5	6
6	5
7	4
8	3
9	2
⋯ 11 more passes ⋯
21	1
22	0

20 passes — pass 1 is the card above
pass	`i`	`sum`
1	1	0 → 1
2	2	1 → 3
3	3	3 → 6
4	4	6 → 10
5	5	10 → 15
6	6	15 → 21
7	7	21 → 28
8	8	28 → 36
9	9	36 → 45
⋯ 9 more passes ⋯
19	9	36 → 45
20	10	45 → 55

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

All 8 passes — pass 1 is the card above
pass	`i`	`result`
1	0	1 → 2
2	1	2 → 4
3	2	4 → 8
4	3	8 → 16
5	4	16 → 32
6	5	32 → 64
7	6	64 → 128
8	7	128 → 256

Base Case Importance

Missing or unreachable base cases lead to stack overflow. Keep examples bounded for tracing.

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

                            public class BaseCase {
    public static int infiniteRecursion(int n) {
        return infiniteRecursion(n - 1);
    }
    public static int countdown(int n) {
        if (n <= 0) {
            System.out.println("Liftoff!");
            return 0;
        }
        System.out.println(n);
        return countdown(n - 1);
    }
    public static int badBaseCase(int n) {
        if (n == 0) {
            return 0;
        }
        return badBaseCase(n - 1);
    }
    public static void main(String[] args) {
        System.out.println("Countdown with proper base case:");
        countdown(5);

        System.out.println("\nTrying infinite recursion with small depth:");
        System.out.println("Skipped: calling infiniteRecursion would overflow the stack.");

        System.out.println("\nWrong base case with positive input (safe):");
        badBaseCase(3);
    }
}

                        
1public static void main(String[] args)⋯18}19public static void main(String[] args) {20    System.out.println("Countdown with proper base case:");21    countdown(5);⋯outputCountdown with proper base case:
2public static int countdown(int n)pass 1 of 6⋯4}5public static int countdown(int n5) {6    if (n <= 0) {7        System.out.println("Liftoff!");8        return 0;9    }10    System.out.println(n5);11    return countdown(n5 - 1);12}⋯output5All 6 passes — pass 1 is the card abovepassn
15
24
33
42
51
60
3if (n <= 0)⋯5public static int countdown(int n) {6    if (n0 <= 0) {7        System.out.println("Liftoff!");8        return 0;9    }⋯outputLiftoff!
4countdown(5);⋯20    System.out.println("Countdown with proper base case:");21    countdown(5);2223    System.out.println("\nTrying infinite recursion with small depth:");24    System.out.println("Skipped: calling infiniteRecursion would overflow the stack.");2526    System.out.println("\nWrong base case with positive input (safe):");27    badBaseCase(3);28}⋯output
Trying infinite recursion with small depth:
Skipped: calling infiniteRecursion would overflow the stack.

Wrong base case with positive input (safe):
5public static int badBaseCase(int n)pass 1 of 4⋯12}13public static int badBaseCase(int n3) {14    if (n == 0) {15        return 0;16    }17    return badBaseCase(n3 - 1);18}⋯All 4 passes — pass 1 is the card abovepassn
13
22
31
40
6if (n == 0)⋯13public static int badBaseCase(int n) {14    if (n0 == 0) {15        return 0;16    }⋯
7badBaseCase(3);⋯26    System.out.println("\nWrong base case with positive input (safe):");27    badBaseCase(3);28}⋯

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

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

Fibonacci Example

Fibonacci shows how multiple recursive calls can grow quickly.

                            example
                            maxN = 6, countedN = 6 (default)maxN = 8countedN = 8
                        

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

                            public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
    private static int callCount = 0;

    public static int fibonacciCounted(int n) {
        callCount++;

        if (n <= 1) {
            return n;
        }

        return fibonacciCounted(n - 1) + fibonacciCounted(n - 2);
    }
    public static void main(String[] args) {
        int maxN = 6;
        int countedN = 6;

        System.out.println("Fibonacci sequence:");
        for (int i = 0; i <= maxN; i++) {
            System.out.println("fib(" + i + ") = " + fibonacci(i));
        }
        callCount = 0;
        int result = fibonacciCounted(countedN);
        System.out.println("\nfib(" + countedN + ") = " + result +
                           ", required " + callCount + " calls");
    }
}
public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
    private static int callCount = 0;

    public static int fibonacciCounted(int n) {
        callCount++;

        if (n <= 1) {
            return n;
        }

        return fibonacciCounted(n - 1) + fibonacciCounted(n - 2);
    }
    public static void main(String[] args) {
        int maxN = 8;
        int countedN = 6;

        System.out.println("Fibonacci sequence:");
        for (int i = 0; i <= maxN; i++) {
            System.out.println("fib(" + i + ") = " + fibonacci(i));
        }
        callCount = 0;
        int result = fibonacciCounted(countedN);
        System.out.println("\nfib(" + countedN + ") = " + result +
                           ", required " + callCount + " calls");
    }
}
public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
    private static int callCount = 0;

    public static int fibonacciCounted(int n) {
        callCount++;

        if (n <= 1) {
            return n;
        }

        return fibonacciCounted(n - 1) + fibonacciCounted(n - 2);
    }
    public static void main(String[] args) {
        int maxN = 6;
        int countedN = 8;

        System.out.println("Fibonacci sequence:");
        for (int i = 0; i <= maxN; i++) {
            System.out.println("fib(" + i + ") = " + fibonacci(i));
        }
        callCount = 0;
        int result = fibonacciCounted(countedN);
        System.out.println("\nfib(" + countedN + ") = " + result +
                           ", required " + callCount + " calls");
    }
}

                        
1maxN ← 6, countedN ← 6⋯18}19public static void main(String[] args) {20    int maxN→ 6 = 6; //@maxN=6, 821    int countedN→ 6 = 6; //@countedN=6, 82223    System.out.println("Fibonacci sequence:");24    for (int i = 0; i <= maxN; i++) {⋯outputFibonacci sequence:
2for (int i = 0; i <= maxN; i++)pass 1 of 7⋯23System.out.println("Fibonacci sequence:");24for (int i0 = 0; i <= maxN6; i++) {25    System.out.println("fib(" + i0 + ") = " + fibonacci(i));26}⋯All 7 passes — pass 1 is the card abovepassi
10
21
32
43
54
65
76
3public static int fibonacci(int n)pass 1 of 591public class Fibonacci {2    public static int fibonacci(int n0) {3        if (n <= 1) {⋯59 passes — pass 1 is the card abovepassn
10
21
32
41
50
63
72
81
90
⋯ 48 more passes ⋯
581
590
4if (n <= 1)pass 1 of 33⋯2public static int fibonacci(int n) {3    if (n0 <= 1) {4        return n0;5    }⋯33 passes — pass 1 is the card abovepassn
10
21
31
40
51
60
71
81
90
⋯ 22 more passes ⋯
321
330
5System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i0 + ") = " + fibonacci(i));26}⋯outputfib(0) = 0
6System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i1 + ") = " + fibonacci(i));26}⋯outputfib(1) = 1
7System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i2 + ") = " + fibonacci(i));26}⋯outputfib(2) = 1
8System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i3 + ") = " + fibonacci(i));26}⋯outputfib(3) = 2
9System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i4 + ") = " + fibonacci(i));26}⋯outputfib(4) = 3
10System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i5 + ") = " + fibonacci(i));26}⋯outputfib(5) = 5
11System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i6 + ") = " + fibonacci(i));26}⋯outputfib(6) = 8
12callCount ← 0⋯26}27callCount→ 0 = 0;28int result = fibonacciCounted(countedN6);29System.out.println("\nfib(" + countedN + ") = " + result +⋯
13callCount ← 1pass 1 of 25⋯10public static int fibonacciCounted(int n6) {11    callCount→ 1++;1213    if (n <= 1) {14        return n;15    }1617    return fibonacciCounted(n6 - 1) + fibonacciCounted(n - 2);18}⋯25 passes — pass 1 is the card abovepassncallCount
160 → 1
251 → 2
342 → 3
433 → 4
524 → 5
615 → 6
706 → 7
817 → 8
928 → 9
⋯ 14 more passes ⋯
24123 → 24
25024 → 25
14if (n <= 1)pass 1 of 13⋯13if (n1 <= 1) {14    return n1;15}⋯13 passes — pass 1 is the card abovepassn
11
20
31
41
50
61
70
81
91
⋯ 2 more passes ⋯
121
130
15result ← 8⋯27    callCount = 0;28    int result→ 8 = fibonacciCounted(countedN6);29    System.out.println("\nfib(" + countedN6 + ") = " + result8 +30                       ", required " + callCount25 + " calls");31}⋯output
fib(6) = 8, required 25 calls
1maxN ← 8, countedN ← 6⋯18}19public static void main(String[] args) {20    int maxN→ 8 = 8;21    int countedN→ 6 = 6;2223    System.out.println("Fibonacci sequence:");24    for (int i = 0; i <= maxN; i++) {⋯outputFibonacci sequence:
2for (int i = 0; i <= maxN; i++)pass 1 of 9⋯23System.out.println("Fibonacci sequence:");24for (int i0 = 0; i <= maxN8; i++) {25    System.out.println("fib(" + i0 + ") = " + fibonacci(i));26}⋯All 9 passes — pass 1 is the card abovepassi
10
21
32
43
54
65
76
87
98
3public static int fibonacci(int n)pass 1 of 1671public class Fibonacci {2    public static int fibonacci(int n0) {3        if (n <= 1) {⋯167 passes — pass 1 is the card abovepassn
10
21
32
41
50
63
72
81
90
⋯ 156 more passes ⋯
1661
1670
4if (n <= 1)pass 1 of 88⋯2public static int fibonacci(int n) {3    if (n0 <= 1) {4        return n0;5    }⋯88 passes — pass 1 is the card abovepassn
10
21
31
40
51
60
71
81
90
⋯ 77 more passes ⋯
871
880
5System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i0 + ") = " + fibonacci(i));26}⋯outputfib(0) = 0
6System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i1 + ") = " + fibonacci(i));26}⋯outputfib(1) = 1
7System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i2 + ") = " + fibonacci(i));26}⋯outputfib(2) = 1
8System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i3 + ") = " + fibonacci(i));26}⋯outputfib(3) = 2
9System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i4 + ") = " + fibonacci(i));26}⋯outputfib(4) = 3
10System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i5 + ") = " + fibonacci(i));26}⋯outputfib(5) = 5
11System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i6 + ") = " + fibonacci(i));26}⋯outputfib(6) = 8
12System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i7 + ") = " + fibonacci(i));26}⋯outputfib(7) = 13
13System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i8 + ") = " + fibonacci(i));26}⋯outputfib(8) = 21
14callCount ← 0⋯26}27callCount→ 0 = 0;28int result = fibonacciCounted(countedN6);29System.out.println("\nfib(" + countedN + ") = " + result +⋯
15callCount ← 1pass 1 of 25⋯10public static int fibonacciCounted(int n6) {11    callCount→ 1++;1213    if (n <= 1) {14        return n;15    }1617    return fibonacciCounted(n6 - 1) + fibonacciCounted(n - 2);18}⋯25 passes — pass 1 is the card abovepassncallCount
160 → 1
251 → 2
342 → 3
433 → 4
524 → 5
615 → 6
706 → 7
817 → 8
928 → 9
⋯ 14 more passes ⋯
24123 → 24
25024 → 25
16if (n <= 1)pass 1 of 13⋯13if (n1 <= 1) {14    return n1;15}⋯13 passes — pass 1 is the card abovepassn
11
20
31
41
50
61
70
81
91
⋯ 2 more passes ⋯
121
130
17result ← 8⋯27    callCount = 0;28    int result→ 8 = fibonacciCounted(countedN6);29    System.out.println("\nfib(" + countedN6 + ") = " + result8 +30                       ", required " + callCount25 + " calls");31}⋯output
fib(6) = 8, required 25 calls
1maxN ← 6, countedN ← 8⋯18}19public static void main(String[] args) {20    int maxN→ 6 = 6;21    int countedN→ 8 = 8;2223    System.out.println("Fibonacci sequence:");24    for (int i = 0; i <= maxN; i++) {⋯outputFibonacci sequence:
2for (int i = 0; i <= maxN; i++)pass 1 of 7⋯23System.out.println("Fibonacci sequence:");24for (int i0 = 0; i <= maxN6; i++) {25    System.out.println("fib(" + i0 + ") = " + fibonacci(i));26}⋯All 7 passes — pass 1 is the card abovepassi
10
21
32
43
54
65
76
3public static int fibonacci(int n)pass 1 of 591public class Fibonacci {2    public static int fibonacci(int n0) {3        if (n <= 1) {⋯59 passes — pass 1 is the card abovepassn
10
21
32
41
50
63
72
81
90
⋯ 48 more passes ⋯
581
590
4if (n <= 1)pass 1 of 33⋯2public static int fibonacci(int n) {3    if (n0 <= 1) {4        return n0;5    }⋯33 passes — pass 1 is the card abovepassn
10
21
31
40
51
60
71
81
90
⋯ 22 more passes ⋯
321
330
5System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i0 + ") = " + fibonacci(i));26}⋯outputfib(0) = 0
6System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i1 + ") = " + fibonacci(i));26}⋯outputfib(1) = 1
7System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i2 + ") = " + fibonacci(i));26}⋯outputfib(2) = 1
8System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i3 + ") = " + fibonacci(i));26}⋯outputfib(3) = 2
9System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i4 + ") = " + fibonacci(i));26}⋯outputfib(4) = 3
10System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i5 + ") = " + fibonacci(i));26}⋯outputfib(5) = 5
11System.out.println("fib(" + i + ") = " + fibonacci(i));⋯24for (int i = 0; i <= maxN; i++) {25    System.out.println("fib(" + i6 + ") = " + fibonacci(i));26}⋯outputfib(6) = 8
12callCount ← 0⋯26}27callCount→ 0 = 0;28int result = fibonacciCounted(countedN8);29System.out.println("\nfib(" + countedN + ") = " + result +⋯
13callCount ← 1pass 1 of 67⋯10public static int fibonacciCounted(int n8) {11    callCount→ 1++;1213    if (n <= 1) {14        return n;15    }1617    return fibonacciCounted(n8 - 1) + fibonacciCounted(n - 2);18}⋯67 passes — pass 1 is the card abovepassncallCount
180 → 1
271 → 2
362 → 3
453 → 4
544 → 5
635 → 6
726 → 7
817 → 8
908 → 9
⋯ 56 more passes ⋯
66165 → 66
67066 → 67
14if (n <= 1)pass 1 of 34⋯13if (n1 <= 1) {14    return n1;15}⋯34 passes — pass 1 is the card abovepassn
11
20
31
41
50
61
70
81
91
⋯ 23 more passes ⋯
331
340
15result ← 21⋯27    callCount = 0;28    int result→ 21 = fibonacciCounted(countedN8);29    System.out.println("\nfib(" + countedN8 + ") = " + result21 +30                       ", required " + callCount67 + " calls");31}⋯output
fib(8) = 21, required 67 calls

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

59 passes — pass 1 is the card above
pass	`n`
1	0
2	1
3	2
4	1
5	0
6	3
7	2
8	1
9	0
⋯ 48 more passes ⋯
58	1
59	0

33 passes — pass 1 is the card above
pass	`n`
1	0
2	1
3	1
4	0
5	1
6	0
7	1
8	1
9	0
⋯ 22 more passes ⋯
32	1
33	0

25 passes — pass 1 is the card above
pass	`n`	`callCount`
1	6	0 → 1
2	5	1 → 2
3	4	2 → 3
4	3	3 → 4
5	2	4 → 5
6	1	5 → 6
7	0	6 → 7
8	1	7 → 8
9	2	8 → 9
⋯ 14 more passes ⋯
24	1	23 → 24
25	0	24 → 25

13 passes — pass 1 is the card above
pass	`n`
1	1
2	0
3	1
4	1
5	0
6	1
7	0
8	1
9	1
⋯ 2 more passes ⋯
12	1
13	0

All 9 passes — pass 1 is the card above
pass	`i`
1	0
2	1
3	2
4	3
5	4
6	5
7	6
8	7
9	8

167 passes — pass 1 is the card above
pass	`n`
1	0
2	1
3	2
4	1
5	0
6	3
7	2
8	1
9	0
⋯ 156 more passes ⋯
166	1
167	0

88 passes — pass 1 is the card above
pass	`n`
1	0
2	1
3	1
4	0
5	1
6	0
7	1
8	1
9	0
⋯ 77 more passes ⋯
87	1
88	0

25 passes — pass 1 is the card above
pass	`n`	`callCount`
1	6	0 → 1
2	5	1 → 2
3	4	2 → 3
4	3	3 → 4
5	2	4 → 5
6	1	5 → 6
7	0	6 → 7
8	1	7 → 8
9	2	8 → 9
⋯ 14 more passes ⋯
24	1	23 → 24
25	0	24 → 25

13 passes — pass 1 is the card above
pass	`n`
1	1
2	0
3	1
4	1
5	0
6	1
7	0
8	1
9	1
⋯ 2 more passes ⋯
12	1
13	0

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

59 passes — pass 1 is the card above
pass	`n`
1	0
2	1
3	2
4	1
5	0
6	3
7	2
8	1
9	0
⋯ 48 more passes ⋯
58	1
59	0

33 passes — pass 1 is the card above
pass	`n`
1	0
2	1
3	1
4	0
5	1
6	0
7	1
8	1
9	0
⋯ 22 more passes ⋯
32	1
33	0

67 passes — pass 1 is the card above
pass	`n`	`callCount`
1	8	0 → 1
2	7	1 → 2
3	6	2 → 3
4	5	3 → 4
5	4	4 → 5
6	3	5 → 6
7	2	6 → 7
8	1	7 → 8
9	0	8 → 9
⋯ 56 more passes ⋯
66	1	65 → 66
67	0	66 → 67

34 passes — pass 1 is the card above
pass	`n`
1	1
2	0
3	1
4	1
5	0
6	1
7	0
8	1
9	1
⋯ 23 more passes ⋯
33	1
34	0

Practical Tree Shape

Recursive code often maps cleanly to tree-like structures.

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

                            public class Practical {
    public static void printStructure(String name, int depth) {
        if (depth <= 0) {
            return;
        }
        String indent = "  ".repeat(4 - depth);
        System.out.println(indent + "├── " + name);
        if (depth > 1) {
            printStructure("sub_" + name + "_1", depth - 1);
            printStructure("sub_" + name + "_2", depth - 1);
        }
    }
    public static int treeSize(int depth) {
        if (depth <= 0) {
            return 1;
        }
        return 1 + treeSize(depth - 1) + treeSize(depth - 1);
    }
    public static int findDepth(int nodeCount, int currentDepth) {
        if (nodeCount <= 1) {
            return currentDepth;
        }
        return findDepth(nodeCount / 2, currentDepth + 1);
    }
    public static void main(String[] args) {
        System.out.println("Directory structure (depth 3):");
        printStructure("root", 3);

        System.out.println("\nTree sizes:");
        for (int depth = 0; depth <= 4; depth++) {
            System.out.println("  Depth " + depth + ": " + treeSize(depth) + " nodes");
        }

        System.out.println("\nDepth calculations:");
        int[] nodeCounts = {1, 2, 4, 8, 16, 32};
        for (int count : nodeCounts) {
            System.out.println("  " + count + " nodes → depth " + findDepth(count, 0));
        }
    }
}

                        
1public static void main(String[] args)⋯24}25public static void main(String[] args) {26    System.out.println("Directory structure (depth 3):");27    printStructure("root", 3);⋯outputDirectory structure (depth 3):
2indent ←   pass 1 of 71public class Practical {2    public static void printStructure(String nameroot, int depth3) {3        if (depth <= 0) {4            return;5        }6        String indent→    = "  ".repeat(4 - depth3);7        System.out.println(indent   + "├── " + nameroot);8        if (depth > 1) {⋯output  ├── rootAll 7 passes — pass 1 is the card abovepassindentnamedepth
1  root3
2    sub_root_12
3      sub_sub_root_1_11
4      sub_sub_root_1_2 → root1 → 3
5    sub_root_22
6      sub_sub_root_2_11
7      sub_sub_root_2_2 → root1 → 3
3if (depth > 1)pass 1 of 3⋯7System.out.println(indent + "├── " + name);8if (depth3 > 1) {9    printStructure("sub_" + nameroot + "_1", depth3 - 1);10    printStructure("sub_" + name + "_2", depth - 1);⋯All 3 passes — pass 1 is the card abovepassdepthname
13root
22sub_root_1
32sub_root_2
4printStructure("root", 3);⋯26System.out.println("Directory structure (depth 3):");27printStructure("root", 3);2829System.out.println("\nTree sizes:");30for (int depth = 0; depth <= 4; depth++) {⋯output
Tree sizes:
5for (int depth = 0; depth <= 4; depth++)pass 1 of 5⋯29System.out.println("\nTree sizes:");30for (int depth0 = 0; depth <= 4; depth++) {31    System.out.println("  Depth " + depth0 + ": " + treeSize(depth) + " nodes");32}⋯All 5 passes — pass 1 is the card abovepassdepth
10
21
32
43
54
6public static int treeSize(int depth)pass 1 of 57⋯12}13public static int treeSize(int depth0) {14    if (depth <= 0) {⋯57 passes — pass 1 is the card abovepassdepth
10
21
30
40
52
61
70
80
91
⋯ 46 more passes ⋯
560
570
7if (depth <= 0)pass 1 of 31⋯13public static int treeSize(int depth) {14    if (depth0 <= 0) {15        return 1;16    }⋯
8System.out.println("  Depth " + depth + ": " + treeSize(depth) + " nod…⋯30for (int depth = 0; depth <= 4; depth++) {31    System.out.println("  Depth " + depth0 + ": " + treeSize(depth) + " nodes");32}⋯output  Depth 0: 1 nodes
9System.out.println("  Depth " + depth + ": " + treeSize(depth) + " nod…⋯30for (int depth = 0; depth <= 4; depth++) {31    System.out.println("  Depth " + depth1 + ": " + treeSize(depth) + " nodes");32}⋯output  Depth 1: 3 nodes
10System.out.println("  Depth " + depth + ": " + treeSize(depth) + " nod…⋯30for (int depth = 0; depth <= 4; depth++) {31    System.out.println("  Depth " + depth2 + ": " + treeSize(depth) + " nodes");32}⋯output  Depth 2: 7 nodes
11System.out.println("  Depth " + depth + ": " + treeSize(depth) + " nod…⋯30for (int depth = 0; depth <= 4; depth++) {31    System.out.println("  Depth " + depth3 + ": " + treeSize(depth) + " nodes");32}⋯output  Depth 3: 15 nodes
12System.out.println("  Depth " + depth + ": " + treeSize(depth) + " nod…⋯30for (int depth = 0; depth <= 4; depth++) {31    System.out.println("  Depth " + depth4 + ": " + treeSize(depth) + " nodes");32}⋯output  Depth 4: 31 nodes
13int[] nodeCounts = {1, 2, 4, 8, 16, 32};⋯34System.out.println("\nDepth calculations:");35int[] nodeCounts = {1, 2, 4, 8, 16, 32};36for (int count : nodeCounts) {⋯output
Depth calculations:
14for (int count : nodeCounts)pass 1 of 6⋯35int[] nodeCounts = {1, 2, 4, 8, 16, 32};36for (int count1 : nodeCounts) {37    System.out.println("  " + count1 + " nodes → depth " + findDepth(count, 0));38}⋯All 6 passes — pass 1 is the card abovepasscount
11
22
34
48
516
632
15public static int findDepth(int nodeCount, int currentDepth)pass 1 of 21⋯18}19public static int findDepth(int nodeCount1, int currentDepth0) {20    if (nodeCount <= 1) {⋯21 passes — pass 1 is the card abovepassnodeCountcurrentDepth
110
220
311
440
521
612
780
841
922
⋯ 10 more passes ⋯
2024
2115
16if (nodeCount <= 1)pass 1 of 6⋯19public static int findDepth(int nodeCount, int currentDepth) {20    if (nodeCount1 <= 1) {21        return currentDepth0;22    }⋯All 6 passes — pass 1 is the card abovepasscurrentDepth
10
21
32
43
54
65
17System.out.println("  " + count + " nodes → depth " + findDepth(count,…⋯36for (int count : nodeCounts) {37    System.out.println("  " + count1 + " nodes → depth " + findDepth(count, 0));38}⋯output  1 nodes → depth 0
18System.out.println("  " + count + " nodes → depth " + findDepth(count,…⋯36for (int count : nodeCounts) {37    System.out.println("  " + count2 + " nodes → depth " + findDepth(count, 0));38}⋯output  2 nodes → depth 1
19System.out.println("  " + count + " nodes → depth " + findDepth(count,…⋯36for (int count : nodeCounts) {37    System.out.println("  " + count4 + " nodes → depth " + findDepth(count, 0));38}⋯output  4 nodes → depth 2
20System.out.println("  " + count + " nodes → depth " + findDepth(count,…⋯36for (int count : nodeCounts) {37    System.out.println("  " + count8 + " nodes → depth " + findDepth(count, 0));38}⋯output  8 nodes → depth 3
21System.out.println("  " + count + " nodes → depth " + findDepth(count,…⋯36for (int count : nodeCounts) {37    System.out.println("  " + count16 + " nodes → depth " + findDepth(count, 0));38}⋯output  16 nodes → depth 4
22System.out.println("  " + count + " nodes → depth " + findDepth(count,…⋯36for (int count : nodeCounts) {37    System.out.println("  " + count32 + " nodes → depth " + findDepth(count, 0));38}⋯output  32 nodes → depth 5

All 7 passes — pass 1 is the card above
pass	`name`	`depth`
1	root	3
2	sub_root_1	2
3	sub_sub_root_1_1	1
4	sub_sub_root_1_2 → root	1 → 3
5	sub_root_2	2
6	sub_sub_root_2_1	1
7	sub_sub_root_2_2 → root	1 → 3

All 3 passes — pass 1 is the card above
pass	`depth`	`name`
1	3	root
2	2	sub_root_1
3	2	sub_root_2

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

57 passes — pass 1 is the card above
pass	`depth`
1	0
2	1
3	0
4	0
5	2
6	1
7	0
8	0
9	1
⋯ 46 more passes ⋯
56	0
57	0

All 6 passes — pass 1 is the card above
pass	`count`
1	1
2	2
3	4
4	8
5	16
6	32

21 passes — pass 1 is the card above
pass	`nodeCount`	`currentDepth`
1	1	0
2	2	0
3	1	1
4	4	0
5	2	1
6	1	2
7	8	0
8	4	1
9	2	2
⋯ 10 more passes ⋯
20	2	4
21	1	5

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

Exercise: Practical.java

Implement a recursive method to calculate the sum of digits in a positive integer