CSE1030 Lab 07

Recursion

Week of Mar 10
Due: before Mar 21 11:59PM

Introduction

This lab has you implement four recursive algorithms. You should review the course notes and lecture slides before attempting this lab.

For Questions 1–3, you are given examples that should help you determine the base case(s) and the recursive invocation. For Question 4, you need to find the base cases and recursive invocations on your own.

Starter code is available here.

A JUnit tester is available here.

Please submit your solution before the next lab.

Question 1: Integer Division as Recursion

Integer division can be implemented by recursive subtraction. For example:

  60 / 12
= 1 + (60 - 12) / 12                      recursive call
= 1 + 48 / 12
= 1 + 1 + (48 - 12) / 12                  recursive call
= 1 + 1 + 36 / 12
= 1 + 1 + 1 + (36 - 12) / 12              recursive call
= 1 + 1 + 1 + 24 / 12
= 1 + 1 + 1 + 1 + (24 - 12) / 12          recursive call
= 1 + 1 + 1 + 1 + 12 / 12
= 1 + 1 + 1 + 1 + 1 + (12 - 12) / 12      recursive call
= 1 + 1 + 1 + 1 + 1 + 0 / 12              base case          
= 1 + 1 + 1 + 1 + 1 + 0     
= 5

Another example:

  27 / 8
= 1 + (27 - 8) / 8                        recursive call
= 1 + 19 / 8
= 1 + 1 + (19 - 8) / 8                    recursive call
= 1 + 1 + 11 / 8
= 1 + 1 + 1 + (11 - 8) / 8                recursive call
= 1 + 1 + 1 + 3 / 12                      base case
= 1 + 1 + 1 + 0
= 3

Implement the method public static int divide(int a, int b) using recursive subtraction.

Question 2: Replace all occurrences of a character in a string

Replacing all occurrences of a given character oldChar in a string can be done recursively by examining the first character of the string; if the first character is the same as oldChar then the first character is replaced by the new character newChar, otherwise the first character is retained. The rest of the string (from the second character onwards) is then recursively processed. For example, consider replacing all 't' characters with 'p' in the string "turtle":

  replace("turtle", 't', 'p')
= "p" + replace("urtle", 't', 'p')
= "p" + ("u" + replace("rtle", 't', 'p'))
= "p" + ("u" + ("r" + replace("tle", 't', 'p')))
= "p" + ("u" + ("r" + ("p" + replace("le", 't', 'p'))))
= "p" + ("u" + ("r" + ("p" + ("l" + replace("e", 't', 'p')))))
= "p" + ("u" + ("r" + ("p" + ("l" + ("e" + replace("", 't', 'p'))))))    base case, return ""
= "p" + ("u" + ("r" + ("p" + ("l" + ("e")))))                            return "e"
= "p" + ("u" + ("r" + ("p" + ("le"))))                                   return "le"
= "p" + ("u" + ("r" + ("ple")))                                          return "ple"
= "p" + ("u" + ("rple"))                                                 return "rple"
= "p" + ("urple")                                                        return "urple"
= "purple"                                                               return "purple"

Implement the method public static String replace(String s, oldChar c, newChar c) using recursion. You must not use a collection, and the only methods that you may use from String are substring, startsWith, length, and isEmpty.

Question 3: Move the smallest element of a list to the front of the list

The sorting algorithm selection sort requires the ability to move the smallest element of a list to the front of the list. Moving the smallest element to the front of the list can be done using recursion as shown in the figure below (for a list containing the numbers 0 through 9):

Implement the method public void minToFront(List<Integer> t) using the recursive algorithm illustrated in the figure. You can recursively call minToFront but otherwise, you can only use methods from List, and of those methods you can only use get, set, size, and subList.

Question 4: Left or right?

Consider a puzzle made up of a list of non-negative integer values (an example is shown in the figure below). You start at the first element in the list, and the goal is to reach the last element of the list (whose value is always zero). You may move left or right in the list, and the number of steps that you can take is given by the element that you are currently on. You may not move outside of the list; this means that your first move must be to the right (because you start at the left most element). You may assume that exactly one zero appears in the puzzle and that it is always the last (rightmost) element of the list.

The puzzle below can be solved by making the sequence of moves shown:

Any given puzzle may have more than one solution, and it may have no solution. Write the recursive method public boolean isSolvable(int index, List<Integer> t) that determines if a puzzle represented by a list t is solvable or not; index is the index in the list where you are currently at. You must not modify the original list; however, you can make a copy of the list and modify the copy.

You should try to solve this problem without significant help from the teaching assistants or your professor. Here are some hints to help you:

Submit your work

submit 1030 L7 Lab7.java