CS 112
Spring 2024

Lab 5: Recursion

Creating the necessary folder

Make sure to create a subfolder called lab5 within your cs112 folder, and put all of the files for this lab in that folder.

Task 1: Recursion, the basics

In class we’ve begun talking about how recursion works, how to understand recursive methods, and how to trace them. With lab we’ll be talking a bit about how to design recursive methods – 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 – i.e., if it reads the same backwards as it does forwards.

  1. Begin by downloading the following starter file to your lab5 folder: RecurPalindrome.java

  2. In VS Code, open your lab5 folder using File->Open Folder, and then click on the name of the downloaded file in the Explorer Pane to open an editor window for it.

  3. Complete the method rPalindrome so that it recursively determines if a string is a palindrome. For simplicity, you can assume 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, and false otherwise. You can use the starter code provided.

Task 2: Tracing a method that makes multiple recursive calls

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;
    }
}

Note: We are using a slightly modified version of the Fibonacci sequence that begins with 1 instead of 0.

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 recursive fib method so that it has only one return statement at the end of the method. Hint: Use a variable for the return value, and initialize that variable to the value that would be returned in the base case. Then modify that variable as needed by making the recursive calls.

    Does the revised version of the method work the same way?

Task 3: More practice with recursive methods

Write a recursive method to solve each of the following:

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

    What happens if you try to compute the factorial of a large number? Why do you think this is the case? How could we accommodate larger results?

  2. Count the number of times that a specific number occurs in an array of integers. To do so, you should write a recursive method with the following header:

    public static int countN(int n, int[] arr, int index) {

    It should determine the number of times that the integer n appears in the portion of the array of arr that goes from the specified index to the end of the array.

    For example, if we have:

    int[] a = {5, 3, 5, 2, 7, 3, 5};

    then:

    • countN(5, a, 0) should return 3, because there are 3 occurrences of the integer 5 in the entire array (i.e., the portion of the array that goes from index 0 to the end of the array).

    • countN(5, a, 1) should return 2, because there are 2 occurrences of the integer 5 in the portion of the array that goes from index 1 to the end of the array.

    • countN(5, a, 3) should return 1, because there is 1 occurrence of the integer 5 in the portion of the array that goes from index 3 to the end of the array.

    Note that the inclusion of the index parameter is what will allow you to reduce the problem when you make the recursive call!

  3. Find the minimum element in an array of integers. Write a recursive method that takes in an array of integers and whatever other parameters are needed, and that returns the smallest integer in the array.

    Hint: You should use an additional parameter to keep track of what portion of the array the current call is focused on, just as we did in the previous problem.

  4. Challenge: The greatest common denominator is a common problem in mathematics. Given two positive numbers, what is the largest factor that divised both integers? Write a recursive method that takes in two integers and finds their greatest common denominator. (Hint: Look up Euclid’s algorithm online.)

Extra Practice!

If you get through the exercises above, congratulations!

For extra practice, try some Practice-It exercises.