17. Recursion Lesson

Recursion

Recursion

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 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
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
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
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
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 grups:

  • 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
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 the ``n``th Fibonacci number based on the code below:

1 /**
2  * Returns 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

Find the recursion tree for fibonacci(5) on VisualAlgo.

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.

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