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
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
Memory state at the breakpoint on line 5 in StackTrace.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 11 in StackTrace.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 17 in StackTrace.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 19 in StackTrace.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 14 in StackTrace.java. [code listing] [download] [open]¶
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
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
Memory state at the breakpoint on line 5 in StackTrace2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 11 in StackTrace2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 17 in StackTrace2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 19 in StackTrace2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 14 in StackTrace2.java. [code listing] [download] [open]¶
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
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
Memory state at the breakpoint on line 3 in StackTrace3.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 7 in StackTrace3.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 7 in StackTrace3.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 7 in StackTrace3.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 7 in StackTrace3.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 12 in StackTrace3.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 12 in StackTrace3.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 12 in StackTrace3.java. [code listing] [download] [open]¶
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.
The output is five stars, with no newline:
*****
Code Visualization
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
Memory state at the breakpoint on line 4 in PrintStars.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 8 in PrintStars.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 14 in PrintStars.java. [code listing] [download] [open]¶
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.
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
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
Memory state at the breakpoint on line 4 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 8 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 24 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 24 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 8 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 24 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 8 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 18 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 8 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 15 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 15 in PrintStars2.java. [code listing] [download] [open]¶
Memory state at the breakpoint on line 15 in PrintStars2.java. [code listing] [download] [open]¶
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
Show it works
Draw out the recursion tree and/or stack trace for
downUp to convince yourself that it works.
Power of Two
Complete Leetcode power of 2 problem.
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.
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.
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