Question

Recursion Exercises

These exercises provide practice with recursion in Java. Please add notes if possible.

Objectives

Module:

• To write recursive solutions for basic problems that require iteration.
• To identify and address base cases in a recursive method.

Reminders during development

• Each of your solutions to the problems below should be in their own method.
• If a method header is provided for a problem, then your solution should have that exact method header. Any changes to the method header will receive a zero for that problem.
• You may not use fields in support of any of your methods. Anyone using a field to help write the logic of a method will receive a zero for that problem.
• Each problem has several test cases, where the method is invoked and there is some type of output shown. You are required to test these cases with your submission. I should be able to run your code once and clearly see where you make the method calls and the expected output.
• You may write other private recursive methods to support a method that you are required to write. You may not call these methods directly in your tests. You must call the public method described in each problem when testing.

Requirements

• It should be easy to see each method in your code submission. Any messy or disorganized submissions will be penalized.
• Any solutions that include any form of loop will not be accepted.

  1

  Write a recursive method that given an array of numbers will return the smallest element in the array. If given an array of length 0 the method will throw an IllegalArgumentException. Your method should have the following header: public int smallest(int[] smallest) { //do something } Test cases: smallest([16, 4, 12, 2, 10]); //2 smallest([-2, 0, 3, -3, 2, -3, -1]); //-3 smallest([]); //results in an exception

• 2

  Write a recursive method that when given a positive integer will report whether the number is odd or even. You may not use the modulus operator in this case. Instead you should use the other arithmetic operators and recursion to discover whether the number is odd or even. Hint: Try using the difference operator repeatedly. Your method should have the following header: public boolean oddOrEven(int num) { //do something } Test cases: oddOrEven(673); //true (odd) oddOrEven(18); //false (even) oddOrEven(19); //true (odd)

Answer 1

Here is the completed code for these methods. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

//method to find the smallest value in an array

public int smallest(int[] smallest) {

    // if array length is 0, throwing an exception

    if (smallest.length == 0) {

         throw new IllegalArgumentException();

    }

    // otherwise calling private helper method to do the recursion and find

    // the smallest value

    return smallest(smallest, 0);

}

// helper method for above method to find the smallest value in an array,

// starting from pos position

private int smallest(int[] array, int pos) {

    // if pos reached array end, returning last element

    if (pos == array.length - 1) {

         return array[pos];

    }

    // storing element at pos

    int value = array[pos];

    // finding and storing the smallest element starting from next position,

    // recursively

    int minRemaining = smallest(array, pos + 1);

    // returning the minimum value among value and minRemaining

    if (value < minRemaining) {

         return value;

    } else {

         return minRemaining;

    }

}

// recursive method to check if num is odd or even. returns true if num is

// odd, else false

public boolean oddOrEven(int num) {

    // if num is negative, throwing an exception

    if (num < 0) {

         throw new IllegalArgumentException();

    }

    // if num is 0, returning false (even)

    if (num == 0) {

         return false;

    }

    // if num is 1, returning true (odd)

    if (num == 1) {

         return true;

    }

    // calling the method recursively, passing num-2, which will eventually

    // end up in either 0 or 1, so that any one of the base cases will be

    // executed

    return oddOrEven(num - 2);

}