Lab 6: Recursion

Task 0: Recursion Review, The basics

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.

We’ll begin by talking about something everyone is familar with, determining if a string is a palindrome. In Problem Set 2 you were asked to write a method that used a loop (iterative solution) to determine if a string was a palindrome. Today we will revisit this, with a recursive solution.

1. Download the template code RecurPalindrome.java. Complete the method rPalindrome which should implement a recursive solution to determine if a string is a palindrome. For simplicity you can asume that the input string is an english word without any spaces or special characters. The method should ultimately return true if the input string is a palindrome, or false otherwise. You can use the starter code provided.

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, this Fibonacci Review will give you an overview and history of the Fibonacci sequence.

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)

1. 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.

2. 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.

3. Re-write the fibonacci recursive method to not use multiple return statements. Does it work the same way?

Task 3: Challenge

Write a recursive method to solve each of the following:

1. 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)

2. Find the product of the integers from 1 through n (this is called the factorial function). If n is zero, return 1. Write a recursive method that takes in an integer and computes (and returns) the factorial of that integer.

   What happens if you try to compute the factorial of a very large number? Why do you think this is the case?

3. Count the number of times a specific number occurs in an array of integers. Write a recursive method that takes in an array of integers and some number n and returns the number of times n occurs in the array. Note we did something simiar in class.

4. Find the minimum element in an array of integers. Write a recursive method that takes in an array of integers and returns the minimum integer in the array.

   Hint: Think through the parameters you need to pass to the last couple of methods.