Lab 6: Recursion

Creating the necessary folder

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

Task 0: Memory Diagrams and the ArrayBag class (from Lab 5)

If you did not complete task 3, part 4 from the previous lab, complete it now:

Download the file for the ArrayBag class and open it: ArrayBag.java

Look at the add() method, which adds a single item to the ArrayBag. Draw a memory diagram (stack and heap) of an ArrayBag object called b as the add() method is called on it for the first time. Show the state of memory before, during, and after the addition of the string “don’t blink”.

Task 1: Palindrome, a recursive solution

In class we’ve begun talking about how recursive methods work, how to understand recursive methods, 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.

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: Recursion with Arrays

On paper, write a static recursive method called countN() that counts the number of times that a specific number occurs in an array of integers.

1. Without writing any code yet, consider the base case and the recursive substructure of this problem. We solved a similar problem in lecture with the numOccur() method. What will be different when working with arrays instead of Strings?

2. Next, determine what the method header will be. Consider the following questions:

   • What information/parameters does the initial call to the method need to provide?

   • What information/parameters does your method need to provide to the next recursive call?

   • What will your method be returning?

3. Now write your base case, then make the recursive call, and complete the one step of processing.

4. Trace through your solution with concrete cases to make sure it works!

Task 3: 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?

Pactice: 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. 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.

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

Last updated on October 9, 2026.