Lab 5: Recursion

Reminder on Lab Policy
Task 0: Recursion Review
Task 1: Designing Recursive Methods
Task 2: Tracing a method that makes multiple recursive calls

Using folders

We strongly encourage you to create a separate folder for each lab and each problem set, so that you can more easily keep track of your work. For example, you could create a folder called lab2 for your work on this lab, and put all of the files for this lab in that folder. If you are working on a lab machine, you will need to create the folder on the Z: drive, so that it won’t be lost when you log out.

Reminder on Lab Policy

Attendance in lab is dependent on whether or not you finish the lab. Make sure to get verbally checked off by the TA before leaving.
You are welcomg to work with a partner during labs, but you should be checked off individually.

Task 0: Recursion Review

Task 1: Designing Recursive Methods

In class we’ve talked a lot about how recursive methods work, how to understand them, and how to trace them out. With lab we’ll be talking a bit about how to design recursive functions or how to break down problems to fit the recursive mold.

On the board we’ll talk about something everyone is familar with, one of your problem sets for determining if an string is a Palindrome.

Write the recursive function called RecurPalindrome.java that takes in a string (you can asume that it’s a english word without any spaces or special characters) and return whether the input string is a Palindrome. You can use the starter code provided.
(Do it on your own as a practice!) The greatest common denominator is a common problem in mathematics. Given two positive numbers, what is the largest factor that divises both integers. Write a recursive function that takes in two integers and finds the greatest common denominator. (Hint: Look up Euclids algorithm)

Task 2: Tracing a method that makes multiple recursive calls

Your work for the following tasks should go on the piece of paper that we give you. Please show your paper to a staff member before you leave the lab.

A number of the algorithms that we consider in CS 112 involve recursive methods in which a given invocation of the method may make two or more recursive calls. To understand how this type of algorithm works, it helps to use a diagram known as a call tree.

Let’s work together to develop a call tree for the execution of the following recursive method. (The method allows us to recursively generate the nth integer in the Fibonacci sequence, although you don’t need to be familiar with that sequence to understand this problem.)

public static int fib(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        int prev1 = fib(n - 2);
        int prev2 = fib(n - 1);
        return prev1 + prev2;
    }
}

Assume that we begin with the following initial call to this method:

fib(4)

Let’s draw a call tree for the sequence of calls that are involved in computing the result of fib(4). As we do so, we’ll number each call of the method in the order in which they are made.
The order in which the calls are made is not the same as the order in which the calls return. A given invocation of the method can’t return until both of the calls that it makes (fib(n - 2) and fib(n - 1)) return.

Underneath your call tree, list the order in which the calls return, as well as their return values. When you refer to a given call in this part of the problem, use its number from the call tree.

For example, the initial call always returns last, so the last line in this part of the problem should look like this:
```
call 1 (fib(4)) returns ...
```
where you replace the ... with its return value.
Re-write the fibonacci recursive method to not use multiple return statements. Does it work the same way?