Goals

To refresh on thinking recursively and writing recursive code.

Setup

Mount the COURSES drive and remember to save everything into STUWORK. If you don’t do this, everything you write will disappear when you log out!!!!

  • Create a new folder in your STUWORK/username folder called RecursionLab
  • Open that folder through VSCode

Exercise 0

Create a new file called Recursion.java in your RecursionLab folder. For this lab, you’ll make several static recursive functions in this class and call them in the main method of your Recursion class. (This will be a good example of when static methods are helpful.)

Exercise 1

a. The website CodingBat has several good practice problems for recursion. Solve the bunny ears problem. You can type your code either in VSCode or the website, but you should test your code on the website and then paste your solution into your VSCode file in Recursion.java.

b. CodingBat does some work behind the scenes to let you just put in the method. To run your methods locally, you’ll need to make them static so that you don’t have to create an instance of Recursion (since that’d be weird), and then call them in main:

public static void main(String[] args) {
    System.out.println(Recursion.bunnyEars2(2));
}

Make sure that your method outputs 5 when the input is 2.

Exercise 2

Write a static recursive method that performs exponentiation: it should return ab for input parameters a and b, which are both positive integers. You should not use built-in exponentiation and are limited to only using multiplication.

Remember to test it in main.

Exercise 3

Finally, you will implement a static recursive mergesort function.

a. Copy over the method merge from this code so that you can focus on the recursive portion of mergesort.

b. A naive version of mergesort requires creating many small arrays. To reduce the space complexity of mergesort, you should create one extra array that can be used by all of the recursive calls. merge assumes that you will pass in this extra array along with the index positions that mark the two subarrays to be merged. Test the provided merge function by using it in main to merge the subarrays [3, 5, 7, 9] and [0, 2, 4, 6]. Note that merge expects these subarrays to be in the same array.

c. Finally, create a recursive static mergesort that follows the steps discussed in class:

  • Check for the base case
  • Otherwise
    • split into two subarrays,
    • use mergesort to sort both subarrays, and
    • use merge to merge the sorted subarrays back together with the items in the correct order

Your mergesort should have the following signature:

public static void mergesort(int[] array, int[] temp, int start, int end)

Extensions

There are several more recursion activities on CodingBat to try if you’d like more practice with recursion. You can also look through the end of chapter exercises from the reading. I also have more recursion exercises for my intro students that you could do in Java (and might have previously done in Python :) ).