17. Recursion Lesson

Recursion

Recursion

To see sample solutions, click on the "Configure activity" button and select "Show solutions" from the menu that appears.

Sample solutions not included, because "Show solutions" was not selected before printing.

Part 1: Understanding the Stack
Code Tracing 1

What is the output of the following code?

When a program returns from a method, how does it know where to return to?

 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
Code Visualization
Step 1 of 11: StackTrace.java:5
 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
Code visualization diagram for cs1302/recursion/StackTrace.java line 5

Memory state at the breakpoint on line 5 in StackTrace.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
Code visualization diagram for cs1302/recursion/StackTrace.java line 6

Memory state at the breakpoint on line 6 in StackTrace.java. [code listing] [download] [open]

main: called

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
Code visualization diagram for cs1302/recursion/StackTrace.java line 11

Memory state at the breakpoint on line 11 in StackTrace.java. [code listing] [download] [open]

main: called

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
Code visualization diagram for cs1302/recursion/StackTrace.java line 12

Memory state at the breakpoint on line 12 in StackTrace.java. [code listing] [download] [open]

main: called
a: called

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
Code visualization diagram for cs1302/recursion/StackTrace.java line 17

Memory state at the breakpoint on line 17 in StackTrace.java. [code listing] [download] [open]

main: called
a: called

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
Code visualization diagram for cs1302/recursion/StackTrace.java line 18

Memory state at the breakpoint on line 18 in StackTrace.java. [code listing] [download] [open]

main: called
a: called
b: called

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
Code visualization diagram for cs1302/recursion/StackTrace.java line 19

Memory state at the breakpoint on line 19 in StackTrace.java. [code listing] [download] [open]

main: called
a: called
b: called
b: return

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
Code visualization diagram for cs1302/recursion/StackTrace.java line 13

Memory state at the breakpoint on line 13 in StackTrace.java. [code listing] [download] [open]

main: called
a: called
b: called
b: return

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
Code visualization diagram for cs1302/recursion/StackTrace.java line 14

Memory state at the breakpoint on line 14 in StackTrace.java. [code listing] [download] [open]

main: called
a: called
b: called
b: return
a: return

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
Code visualization diagram for cs1302/recursion/StackTrace.java line 7

Memory state at the breakpoint on line 7 in StackTrace.java. [code listing] [download] [open]

main: called
a: called
b: called
b: return
a: return

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
Code visualization diagram for cs1302/recursion/StackTrace.java line 8

Memory state at the breakpoint on line 8 in StackTrace.java. [code listing] [download] [open]

main: called
a: called
b: called
b: return
a: return
main: return

>_ Console Output

Call Stack Timeline
 1package cs1302.recursion;
 2
 3public class StackTrace {
 4   public static void main(String[] args) {
 5      System.out.println("main: called");
 6      a();
 7      System.out.println("main: return");
 8   } // main
 9
10   public static void a() {
11      System.out.println("a: called");
12      b();
13      System.out.println("a: return");
14   } // a
15
16   public static void b() {
17      System.out.println("b: called");
18      System.out.println("b: return");
19   } // b
20} // StackTrace
Code visualization diagram for cs1302/recursion/StackTrace.java line 5

Memory state at the breakpoint on line 5 in StackTrace.java. [code listing] [download] [open]

Code visualization diagram for cs1302/recursion/StackTrace.java line 11

Memory state at the breakpoint on line 11 in StackTrace.java. [code listing] [download] [open]

Code visualization diagram for cs1302/recursion/StackTrace.java line 17

Memory state at the breakpoint on line 17 in StackTrace.java. [code listing] [download] [open]

Code visualization diagram for cs1302/recursion/StackTrace.java line 19

Memory state at the breakpoint on line 19 in StackTrace.java. [code listing] [download] [open]

Code visualization diagram for cs1302/recursion/StackTrace.java line 14

Memory state at the breakpoint on line 14 in StackTrace.java. [code listing] [download] [open]

Code visualization diagram for cs1302/recursion/StackTrace.java line 8

Memory state at the breakpoint on line 8 in StackTrace.java. [code listing] [download] [open]

Code Tracing 2

What is the output of the following code?

When a program returns from a method, how does it remember the contents of its local variables?

 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
Code Visualization
Step 1 of 11: StackTrace2.java:5
 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
Code visualization diagram for cs1302/recursion/StackTrace2.java line 5

Memory state at the breakpoint on line 5 in StackTrace2.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
Code visualization diagram for cs1302/recursion/StackTrace2.java line 6

Memory state at the breakpoint on line 6 in StackTrace2.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
Code visualization diagram for cs1302/recursion/StackTrace2.java line 11

Memory state at the breakpoint on line 11 in StackTrace2.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
Code visualization diagram for cs1302/recursion/StackTrace2.java line 12

Memory state at the breakpoint on line 12 in StackTrace2.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
Code visualization diagram for cs1302/recursion/StackTrace2.java line 17

Memory state at the breakpoint on line 17 in StackTrace2.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
Code visualization diagram for cs1302/recursion/StackTrace2.java line 18

Memory state at the breakpoint on line 18 in StackTrace2.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
Code visualization diagram for cs1302/recursion/StackTrace2.java line 19

Memory state at the breakpoint on line 19 in StackTrace2.java. [code listing] [download] [open]

3

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
Code visualization diagram for cs1302/recursion/StackTrace2.java line 13

Memory state at the breakpoint on line 13 in StackTrace2.java. [code listing] [download] [open]

3

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
Code visualization diagram for cs1302/recursion/StackTrace2.java line 14

Memory state at the breakpoint on line 14 in StackTrace2.java. [code listing] [download] [open]

3
2

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
Code visualization diagram for cs1302/recursion/StackTrace2.java line 7

Memory state at the breakpoint on line 7 in StackTrace2.java. [code listing] [download] [open]

3
2

>_ Console Output

 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
Code visualization diagram for cs1302/recursion/StackTrace2.java line 8

Memory state at the breakpoint on line 8 in StackTrace2.java. [code listing] [download] [open]

3
2
1

>_ Console Output

Call Stack Timeline
 1package cs1302.recursion;
 2
 3public class StackTrace2 {
 4    public static void main(String[] args) {
 5        int x = 1;
 6        a();
 7        System.out.println(x);
 8    } // main
 9
10    public static void a() {
11        int x = 2;
12        b();
13        System.out.println(x);
14    } // a
15
16    public static void b() {
17        int x = 3;
18        System.out.println(x);
19    } // b
20} // StackTrace2
Code visualization diagram for cs1302/recursion/StackTrace2.java line 5

Memory state at the breakpoint on line 5 in StackTrace2.java. [code listing] [download] [open]

Code visualization diagram for cs1302/recursion/StackTrace2.java line 11

Memory state at the breakpoint on line 11 in StackTrace2.java. [code listing] [download] [open]

Code visualization diagram for cs1302/recursion/StackTrace2.java line 17

Memory state at the breakpoint on line 17 in StackTrace2.java. [code listing] [download] [open]

Code visualization diagram for cs1302/recursion/StackTrace2.java line 19

Memory state at the breakpoint on line 19 in StackTrace2.java. [code listing] [download] [open]

Code visualization diagram for cs1302/recursion/StackTrace2.java line 14

Memory state at the breakpoint on line 14 in StackTrace2.java. [code listing] [download] [open]

Code visualization diagram for cs1302/recursion/StackTrace2.java line 8

Memory state at the breakpoint on line 8 in StackTrace2.java. [code listing] [download] [open]

Discussion

How does the program "remember" the value of its local variables?

Draw out the stack frames to understand. Can also draw a tree of the calls including the calls to println.

Code Tracing 3

What is the output from the program below:

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code Visualization
Step 1 of 16: StackTrace3.java:3
 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 3

Memory state at the breakpoint on line 3 in StackTrace3.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 7

Memory state at the breakpoint on line 7 in StackTrace3.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 10

Memory state at the breakpoint on line 10 in StackTrace3.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 11

Memory state at the breakpoint on line 11 in StackTrace3.java. [code listing] [download] [open]

3

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 7

Memory state at the breakpoint on line 7 in StackTrace3.java. [code listing] [download] [open]

3

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 10

Memory state at the breakpoint on line 10 in StackTrace3.java. [code listing] [download] [open]

3

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 11

Memory state at the breakpoint on line 11 in StackTrace3.java. [code listing] [download] [open]

3
2

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 7

Memory state at the breakpoint on line 7 in StackTrace3.java. [code listing] [download] [open]

3
2

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 10

Memory state at the breakpoint on line 10 in StackTrace3.java. [code listing] [download] [open]

3
2

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 11

Memory state at the breakpoint on line 11 in StackTrace3.java. [code listing] [download] [open]

3
2
1

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 7

Memory state at the breakpoint on line 7 in StackTrace3.java. [code listing] [download] [open]

3
2
1

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 8

Memory state at the breakpoint on line 8 in StackTrace3.java. [code listing] [download] [open]

3
2
1

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 12

Memory state at the breakpoint on line 12 in StackTrace3.java. [code listing] [download] [open]

3
2
1

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 12

Memory state at the breakpoint on line 12 in StackTrace3.java. [code listing] [download] [open]

3
2
1

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 12

Memory state at the breakpoint on line 12 in StackTrace3.java. [code listing] [download] [open]

3
2
1

>_ Console Output

 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 4

Memory state at the breakpoint on line 4 in StackTrace3.java. [code listing] [download] [open]

3
2
1

>_ Console Output

Call Stack Timeline
 1public class StackTrace3 {
 2    public static void main(String[] args) {
 3        a(3);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace3
Code visualization diagram for StackTrace3.java line 3

Memory state at the breakpoint on line 3 in StackTrace3.java. [code listing] [download] [open]

Code visualization diagram for StackTrace3.java line 7

Memory state at the breakpoint on line 7 in StackTrace3.java. [code listing] [download] [open]

Code visualization diagram for StackTrace3.java line 7

Memory state at the breakpoint on line 7 in StackTrace3.java. [code listing] [download] [open]

Code visualization diagram for StackTrace3.java line 7

Memory state at the breakpoint on line 7 in StackTrace3.java. [code listing] [download] [open]

Code visualization diagram for StackTrace3.java line 7

Memory state at the breakpoint on line 7 in StackTrace3.java. [code listing] [download] [open]

Code visualization diagram for StackTrace3.java line 12

Memory state at the breakpoint on line 12 in StackTrace3.java. [code listing] [download] [open]

Code visualization diagram for StackTrace3.java line 12

Memory state at the breakpoint on line 12 in StackTrace3.java. [code listing] [download] [open]

Code visualization diagram for StackTrace3.java line 12

Memory state at the breakpoint on line 12 in StackTrace3.java. [code listing] [download] [open]

Code visualization diagram for StackTrace3.java line 4

Memory state at the breakpoint on line 4 in StackTrace3.java. [code listing] [download] [open]

Discussion

How do we get it the code above to print the reverse order? See if you can do this by moving lines, but without changing any individual lines.

Trace the calls with the stack trace / recursion tree.

Solution

We could swap the last two lines of the a method to reverse the output. In this scenario, the printing happens after the recursive calls which would reverse the numbers.

Code Tracing 4

What is the output from the program below:

 1public class StackTrace4 {
 2    public static void main(String[] args) {
 3        a(-1);
 4    } // main
 5
 6    public static void a(int num) {
 7        if (num == 0) {
 8            return;
 9        } // if
10        System.out.println(num);
11        a(num - 1);
12    } // a
13
14} // StackTrace4
Part 2: Tracing Recursive Code
Example - PrintStars

Draw the recursion tree for the code below and write the output on your exit ticket:

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Sample Solution

Each node represents a method call. Each printStars call with a positive argument calls print("*") before making the next recursive call. The call to printStars(0) returns without printing or making another recursive call.

main calls printStars(5). Each positive printStars call calls print("*") and then printStars with one less. printStars(0) returns without further calls.

main calls printStars(5). Each positive printStars call calls print("*") and then printStars with one less. printStars(0) returns without further calls.

Fig. 20 Call tree for PrintStars. [svg] [png]

The output is five stars, with no newline:

*****
Code Visualization
Step 1 of 24: PrintStars.java:4
 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 4

Memory state at the breakpoint on line 4 in PrintStars.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 8

Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 12

Memory state at the breakpoint on line 12 in PrintStars.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 13

Memory state at the breakpoint on line 13 in PrintStars.java. [code listing] [download] [open]

*

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 8

Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]

*

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 12

Memory state at the breakpoint on line 12 in PrintStars.java. [code listing] [download] [open]

*

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 13

Memory state at the breakpoint on line 13 in PrintStars.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 8

Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 12

Memory state at the breakpoint on line 12 in PrintStars.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 13

Memory state at the breakpoint on line 13 in PrintStars.java. [code listing] [download] [open]

***

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 8

Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]

***

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 12

Memory state at the breakpoint on line 12 in PrintStars.java. [code listing] [download] [open]

***

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 13

Memory state at the breakpoint on line 13 in PrintStars.java. [code listing] [download] [open]

****

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 8

Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]

****

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 12

Memory state at the breakpoint on line 12 in PrintStars.java. [code listing] [download] [open]

****

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 13

Memory state at the breakpoint on line 13 in PrintStars.java. [code listing] [download] [open]

*****

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 8

Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]

*****

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 9

Memory state at the breakpoint on line 9 in PrintStars.java. [code listing] [download] [open]

*****

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 14

Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]

*****

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 14

Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]

*****

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 14

Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]

*****

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 14

Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]

*****

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 14

Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]

*****

>_ Console Output

 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 5

Memory state at the breakpoint on line 5 in PrintStars.java. [code listing] [download] [open]

*****

>_ Console Output

Call Stack Timeline
 1public class PrintStars {
 2
 3    public static void main(String[] args) {
 4        printStars(5);
 5    } // main
 6
 7    public static void printStars(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        System.out.print("*");
13        printStars(num - 1);
14    } // printStars
15
16} // PrintStars
Code visualization diagram for PrintStars.java line 4

Memory state at the breakpoint on line 4 in PrintStars.java. [code listing] [download] [open]

Code visualization diagram for PrintStars.java line 8

Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]

Code visualization diagram for PrintStars.java line 8

Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]

Code visualization diagram for PrintStars.java line 8

Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]

Code visualization diagram for PrintStars.java line 8

Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]

Code visualization diagram for PrintStars.java line 8

Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]

Code visualization diagram for PrintStars.java line 8

Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]

Code visualization diagram for PrintStars.java line 14

Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]

Code visualization diagram for PrintStars.java line 14

Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]

Code visualization diagram for PrintStars.java line 14

Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]

Code visualization diagram for PrintStars.java line 14

Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]

Code visualization diagram for PrintStars.java line 14

Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]

Code visualization diagram for PrintStars.java line 5

Memory state at the breakpoint on line 5 in PrintStars.java. [code listing] [download] [open]

Example - PrintStars 2

Draw the recursion tree for the code below and write the output on your exit ticket:

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Sample Solution

Each node represents a method call. Read each caller's children from left to right. Each positive printRows call finishes its call to printStars, prints a newline, and then calls printRows again. Calls with an argument of zero return without printing or making further calls.

main calls printRows(3). Each positive printRows call calls printStars with one less, println, and printRows with one less. Each positive printStars call calls print and printStars with one less. Zero is the base case for both methods.

main calls printRows(3). Each positive printRows call calls printStars with one less, println, and printRows with one less. Each positive printStars call calls print and printStars with one less. Zero is the base case for both methods.

Fig. 21 Call tree for PrintStars2. [svg] [png]

The output has three rows: two stars, one star, and an empty row. Each row ends with a newline. Written with \n to show the newlines, the output is **\n*\n\n.

Code Visualization
Step 1 of 37: PrintStars2.java:4
 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 4

Memory state at the breakpoint on line 4 in PrintStars2.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 8

Memory state at the breakpoint on line 8 in PrintStars2.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 12

Memory state at the breakpoint on line 12 in PrintStars2.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 18

Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 22

Memory state at the breakpoint on line 22 in PrintStars2.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 23

Memory state at the breakpoint on line 23 in PrintStars2.java. [code listing] [download] [open]

*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 18

Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]

*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 22

Memory state at the breakpoint on line 22 in PrintStars2.java. [code listing] [download] [open]

*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 23

Memory state at the breakpoint on line 23 in PrintStars2.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 18

Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 19

Memory state at the breakpoint on line 19 in PrintStars2.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 24

Memory state at the breakpoint on line 24 in PrintStars2.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 24

Memory state at the breakpoint on line 24 in PrintStars2.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 13

Memory state at the breakpoint on line 13 in PrintStars2.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 14

Memory state at the breakpoint on line 14 in PrintStars2.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 8

Memory state at the breakpoint on line 8 in PrintStars2.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 12

Memory state at the breakpoint on line 12 in PrintStars2.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 18

Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 22

Memory state at the breakpoint on line 22 in PrintStars2.java. [code listing] [download] [open]

**

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 23

Memory state at the breakpoint on line 23 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 18

Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 19

Memory state at the breakpoint on line 19 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 24

Memory state at the breakpoint on line 24 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 13

Memory state at the breakpoint on line 13 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 14

Memory state at the breakpoint on line 14 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 8

Memory state at the breakpoint on line 8 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 12

Memory state at the breakpoint on line 12 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 18

Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 19

Memory state at the breakpoint on line 19 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 13

Memory state at the breakpoint on line 13 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 14

Memory state at the breakpoint on line 14 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 8

Memory state at the breakpoint on line 8 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 9

Memory state at the breakpoint on line 9 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 15

Memory state at the breakpoint on line 15 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 15

Memory state at the breakpoint on line 15 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 15

Memory state at the breakpoint on line 15 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 5

Memory state at the breakpoint on line 5 in PrintStars2.java. [code listing] [download] [open]

**
*

>_ Console Output

Call Stack Timeline
 1public class PrintStars2 {
 2
 3    public static void main(String[] args) {
 4        printRows(3);
 5    } // main
 6
 7    public static void printRows(int num) {
 8        if(num == 0) {
 9            return;
10        } // if
11
12        printStars(num - 1);
13        System.out.println();
14        printRows(num - 1);
15    } // printRow
16
17    public static void printStars(int num) {
18        if(num == 0) {
19            return;
20        } // if
21
22        System.out.print("*");
23        printStars(num - 1);
24    } // printStars
25
26} // PrintStars2
Code visualization diagram for PrintStars2.java line 4

Memory state at the breakpoint on line 4 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 8

Memory state at the breakpoint on line 8 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 18

Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 18

Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 18

Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 24

Memory state at the breakpoint on line 24 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 24

Memory state at the breakpoint on line 24 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 8

Memory state at the breakpoint on line 8 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 18

Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 18

Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 24

Memory state at the breakpoint on line 24 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 8

Memory state at the breakpoint on line 8 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 18

Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 8

Memory state at the breakpoint on line 8 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 15

Memory state at the breakpoint on line 15 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 15

Memory state at the breakpoint on line 15 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 15

Memory state at the breakpoint on line 15 in PrintStars2.java. [code listing] [download] [open]

Code visualization diagram for PrintStars2.java line 5

Memory state at the breakpoint on line 5 in PrintStars2.java. [code listing] [download] [open]

Part 3: Writing Recursive Algorithms
Problems and Sub-Problems

In general, to create a recursive definition of some concept, we need to establish two things:

  • Base Case: create a non-recursive definition as a "base".

  • Recursive Case: create a definition in terms of itself, changing it somehow (usually towards the base case).

Define problems and sub-problems:

  • We generally want to avoid infinite recursion.

  • Must make progress toward the base case.

  • Want our recursive call to work on a smaller version of the original problem – eventually reaching the base case.

  • Problem: what you're trying to solve.

  • Sub-problem: a smaller version or part of the problem that's easier to solve.

With respect to recursion:

  • Recursive Cases: sub-problems that cannot be solved directly.

  • Base Cases: sub-problems that can be solved easily/directly.

Problem: Length of a Linked List

Discuss the method below in your groups. Then, write the following on your exit tickets:

  • Identify the base case(s)

  • Identify the recursive case(s)

  • Write the algorithm

public static int length(Node head) {

} // length
Solution
public static int length(Node head) {
    // Base Case
    if (head == null) {
        return 0;
    } // if

    int lengthOfSubList = length(head.getNext());
    return 1 + lengthOfSubList;
} // length
Does it work?

To convince yourself that the code works, draw out the recursion tree or the stack trace.

Once we get more practice, we will learn to trust the recursion. If we identify the correct base/recursive case(s), the recursion will work.

Part 4: Example Problems
DownUp
Understanding DownUp

downUp("dawgs") prints the following:

dawgs
dawg
daw
da
d
da
daw
dawg
dawgs

We want a recursive implementation of the method. Answer the following in your groups:

  • What's the base case?

  • What's the recursive case?

Hint: the recursive definition must include a smaller version of the original. So,

downUp("dawgs") =  ______ + downUp(_______) + _______.

Implement DownUp

Create the class cs1302.recursion.DownUp using the following template:

 1public class DownUp {
 2
 3   public static void downUp(String str) {
 4
 5   } // downUp
 6
 7   public static void main(String[] args) {
 8      downUp("Dawgs");
 9   } // main
10
11} // DownUp
Solution
1if(str.length() <= 1) {
2    System.out.println(str);
3} else {
4    System.out.println(str);
5    downUp(str.substring(0, str.length() - 1));
6    System.out.println(str);
7} // if
Code Visualization
Step 1 of 25: DownUp.java:14
 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 14

Memory state at the breakpoint on line 14 in DownUp.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 4

Memory state at the breakpoint on line 4 in DownUp.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 7

Memory state at the breakpoint on line 7 in DownUp.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 8

Memory state at the breakpoint on line 8 in DownUp.java. [code listing] [download] [open]

Dawgs

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 4

Memory state at the breakpoint on line 4 in DownUp.java. [code listing] [download] [open]

Dawgs

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 7

Memory state at the breakpoint on line 7 in DownUp.java. [code listing] [download] [open]

Dawgs

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 8

Memory state at the breakpoint on line 8 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 4

Memory state at the breakpoint on line 4 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 7

Memory state at the breakpoint on line 7 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 8

Memory state at the breakpoint on line 8 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 4

Memory state at the breakpoint on line 4 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 7

Memory state at the breakpoint on line 7 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 8

Memory state at the breakpoint on line 8 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw
Da

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 4

Memory state at the breakpoint on line 4 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw
Da

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 5

Memory state at the breakpoint on line 5 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw
Da

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 11

Memory state at the breakpoint on line 11 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw
Da
D

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 9

Memory state at the breakpoint on line 9 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw
Da
D

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 11

Memory state at the breakpoint on line 11 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw
Da
D
Da

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 9

Memory state at the breakpoint on line 9 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw
Da
D
Da

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 11

Memory state at the breakpoint on line 11 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw
Da
D
Da
Daw

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 9

Memory state at the breakpoint on line 9 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw
Da
D
Da
Daw

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 11

Memory state at the breakpoint on line 11 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw
Da
D
Da
Daw
Dawg

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 9

Memory state at the breakpoint on line 9 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw
Da
D
Da
Daw
Dawg

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 11

Memory state at the breakpoint on line 11 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw
Da
D
Da
Daw
Dawg
Dawgs

>_ Console Output

 1public class DownUp {
 2
 3    public static void downUp(String str) {
 4        if(str.length() <= 1) {
 5            System.out.println(str);
 6        } else {
 7            System.out.println(str);
 8            downUp(str.substring(0, str.length() - 1));
 9            System.out.println(str);
10        } // if
11    } // downUp
12
13    public static void main(String[] args) {
14        downUp("Dawgs");
15    } // main
16
17} // DownUp
Code visualization diagram for DownUp.java line 15

Memory state at the breakpoint on line 15 in DownUp.java. [code listing] [download] [open]

Dawgs
Dawg
Daw
Da
D
Da
Daw
Dawg
Dawgs

>_ Console Output

Show it works

Draw out the recursion tree and/or stack trace for downUp to convince yourself that it works.

Sample Solution

Each node represents a method call. Read sibling calls from left to right; finish each recursive call before continuing to its next sibling. Calls to length and substring are omitted.

main calls downUp("Dawgs"). Each call with more than one character calls println, downUp with the last character removed, and println again. downUp("D") calls println once.

main calls downUp("Dawgs"). Each call with more than one character calls println, downUp with the last character removed, and println again. downUp("D") calls println once.

Fig. 22 Call tree for DownUp. [svg] [png]

Power of Two
Part 5: Fibonacci

With your groups, identify the base case(s) and recursive case(s) for the Fibonacci problem.

  • You may try writing out the Fibonacci sequence and asking: - Where did the fifth number come from? - What about the third? - What about the first? - Okay, which are base cases and which are recursive cases?

Write your answers on your exit ticket. Then, when you are ready, write a method called fibonacci that takes a single integer value (n) and returns with the nth Fibonacci number based on the code below:

1 /**
2  * Returns with the Fibonacci number at index {@code n}.
3  * @param n index
4  * @return Fibonacci number at index {@code n}
5  */
6  public static int fibonacci(int n) {
7      // Implement me
8  } // fibonacci
Solution
1if ((n == 0) || (n == 1)) {
2    return 1;
3} // if
4
5// Might help to break this up into two lines to connect trace the call stack.
6int first = fibonacci(n - 2);
7int second = fibonacci(n - 1);
8return first + second;
Fibonacci Tracing

Draw the recursion tree for fibonacci(3) on your exit ticket.

Traverse the tree. Understand the order of the calls. How many times do you visit fibonacci(5) when performing your traversal (including the initial visit)?

Solution

Each node represents a method call. Read sibling calls from left to right; finish the call to fibonacci(n - 2) before starting the call to fibonacci(n - 1). Each base-case call returns with 1, so the initial call to fibonacci(5) returns with 8.

fibonacci(5) calls fibonacci(3), then fibonacci(4). Each call with argument n greater than one calls fibonacci(n - 2), then fibonacci(n - 1). Calls with argument zero or one return with 1 and make no recursive calls. The tree contains 15 calls, including eight base-case calls.

fibonacci(5) calls fibonacci(3), then fibonacci(4). Each call with argument n greater than one calls fibonacci(n - 2), then fibonacci(n - 1). Calls with argument zero or one return with 1 and make no recursive calls. The tree contains 15 calls, including eight base-case calls.

Fig. 23 Recursion tree for fibonacci(5). [svg] [png]

This recursion tree shows all the frames that execute for fibonacci(5), which may have been hard to see if you're only inspecting the call stack itself over time.

Code Visualization

Use the stepper to compare the active method calls with the recursion tree. The highlighted line is the next line to execute.

Step 1 of 47: Fibonacci.java:32
 1package cs1302.recursion;
 2
 3/** Demonstrates the Fibonacci recursion tree used in Lesson 17. */
 4public final class Fibonacci {
 5
 6    /** Prevents instantiation of this driver class. */
 7    private Fibonacci() {
 8    } // Fibonacci
 9
10    /**
11     * Returns with the Fibonacci number using one for both base cases.
12     * This lesson numbers the sequence as 1, 1, 2, 3, 5, 8, starting at zero.
13     *
14     * @param n a small nonnegative index whose result fits in an int
15     * @return the Fibonacci number at the supplied index
16     */
17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
25
26    /**
27     * Prints the result of the method call shown in the recursion tree.
28     *
29     * @param args command-line arguments (unused)
30     */
31    public static void main(String[] args) {
32        int result = fibonacci(5);
33        System.out.println(result);
34    } // main
35} // Fibonacci
31    public static void main(String[] args) {
32        int result = fibonacci(5);
33        System.out.println(result);
34    } // main
Code visualization diagram for cs1302/recursion/Fibonacci.java line 32

Memory state at the breakpoint on line 32 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 21

Memory state at the breakpoint on line 21 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 21

Memory state at the breakpoint on line 21 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 19

Memory state at the breakpoint on line 19 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 22

Memory state at the breakpoint on line 22 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 21

Memory state at the breakpoint on line 21 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 19

Memory state at the breakpoint on line 19 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 22

Memory state at the breakpoint on line 22 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 19

Memory state at the breakpoint on line 19 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 23

Memory state at the breakpoint on line 23 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 23

Memory state at the breakpoint on line 23 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 22

Memory state at the breakpoint on line 22 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 21

Memory state at the breakpoint on line 21 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 21

Memory state at the breakpoint on line 21 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 19

Memory state at the breakpoint on line 19 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 22

Memory state at the breakpoint on line 22 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 19

Memory state at the breakpoint on line 19 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 23

Memory state at the breakpoint on line 23 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 22

Memory state at the breakpoint on line 22 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 21

Memory state at the breakpoint on line 21 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 19

Memory state at the breakpoint on line 19 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 22

Memory state at the breakpoint on line 22 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 21

Memory state at the breakpoint on line 21 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 19

Memory state at the breakpoint on line 19 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 22

Memory state at the breakpoint on line 22 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 18

Memory state at the breakpoint on line 18 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 19

Memory state at the breakpoint on line 19 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 23

Memory state at the breakpoint on line 23 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 23

Memory state at the breakpoint on line 23 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 23

Memory state at the breakpoint on line 23 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

17    public static int fibonacci(int n) {
18        if ((n == 0) || (n == 1)) {
19            return 1;
20        } // if
21        int first = fibonacci(n - 2);
22        int second = fibonacci(n - 1);
23        return first + second;
24    } // fibonacci
Code visualization diagram for cs1302/recursion/Fibonacci.java line 23

Memory state at the breakpoint on line 23 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

31    public static void main(String[] args) {
32        int result = fibonacci(5);
33        System.out.println(result);
34    } // main
Code visualization diagram for cs1302/recursion/Fibonacci.java line 33

Memory state at the breakpoint on line 33 in Fibonacci.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

31    public static void main(String[] args) {
32        int result = fibonacci(5);
33        System.out.println(result);
34    } // main
Code visualization diagram for cs1302/recursion/Fibonacci.java line 34

Memory state at the breakpoint on line 34 in Fibonacci.java. [code listing] [download] [open]

8

>_ Console Output

Discussion about recursion tree

Some work is repeated. What is the name of the first frame that repeats work (based on traversal order)?

How many times are base cases executed during the recursion for factorial(5)?

Part 6: Find

Find is a command that's similar to the familiar tree command.

Here is some sample output of calling find on a directory called dir:

dir                               // name of the command-line argument
dir/file1.txt                     // same as find dir/file1.txt
dir/file2.txt                     // same as find dir/file2.txt

dir/subdir1                       -----\  These two lines are equivalent to find/subdir1
dir/subdir1/file3.txt             -----/

dir/subdir2
dir/subdir2/file4.txt
dir/subdir2/subdir3
dir/subdir2/subdir3/file5.txt
Implement Find

Create a cs1302.recursion.Find class based on code below.

 1public class Find {
 2
 3    public static void find(File file) {
 4        // TODO implement find
 5    } // find
 6
 7    public static void main(String[] args) {
 8        find(new File(args[0])); // assumes a command-line argument is given.
 9    } // main
10
11} // Find
Solution

One possible solution:

 1public static void find(File file) {
 2    if (file.exists()) {
 3        System.out.println(file.getPath());
 4
 5        if (file.isDirectory()) {
 6            // Get references to all files in this directory
 7            File[] contents = file.listFiles();
 8            if (contents != null) {
 9                for (File f: contents) {
10                    find(f);
11                } // for
12            } // if
13        } // if
14    } // if
15} // find
Find Discussion

Could you write find using loops? Well, how far would you nest the loop? The iterative (looping) solution would be difficult and would likely require you to use the Stack ADT discussed earlier in the semester.

Part 7: Bonus Practice - Tree

Try to implement tree:

$ tree src
|---src
|   |---main
|   |   |---java
|   |   |   |---cs1302
|   |   |   |   |---ce25
|   |   |   |   |   |---Find.java
|   |   |   |   |   |---Tree.java
$ tree src/main/java
|---java
|   |---cs1302
|   |   |---ce25
|   |   |   |---Find.java
|   |   |   |---Tree.java