Building Java Programs

Lab: Recursion

Except where otherwise noted, the contents of this document are Copyright 2019 Stuart Reges and Marty Stepp.

Lab goals

Goals for this problem set:

• write functions that call themselves recursively
• learn to trace and understand recursive code
• think about base cases and recursive cases
• deal with self-similar recursive data

Exercise : mystery2

What output is produced when the given method is called with the given parameters?

public static void mystery2(int n) {
    if (n <= 1) {
        System.out.print(n);
    } else {
        mystery2(n / 2);
        System.out.print(", " + n);
    }
}

Exercise : mystery3

What value is returned when the given method is called with the given parameters?

public static int mystery3(int n) {
    if (n < 0) {
        return -mystery3(-n);
    } else if (n < 10) {
        return n;
    } else {
        return mystery3(n / 10 + n % 10);
    }
}

Exercise : mystery6

What output is produced when the given method is called with the given parameters?

public static void mystery6(int x, int y) {
    if (y == 1) {
        System.out.print(x);
    } else {
        System.out.print(x * y + ", ");
        mystery6(x, y - 1);
        System.out.print(", " + x * y);
    }
}

Exercise : writeChars

Write a recursive method writeChars that accepts an integer n and that prints n characters: The middle character should always be an asterisk ("*"). If you are writing an even number of characters, there will be two asterisks in the middle ("**"). Before the asterisk(s) you should print less-than characters ("<"). After the asterisk(s) you should print greater-than characters (">"). For example, the following calls produce the following output:

Throw an IllegalArgumentException if passed a value less than 1. Do not write any loops.

Exercise : substring

Write a recursive method substring that takes as parameters a string, a start index, and an ending index, and that returns a specified substring of the string. You are implementing a recursive alternative to the standard substring method. As with the standard substring method, your method should return the substring that begins at the start index and that extends to the character just before the ending index. For example, substring("hello", 0, 2) should return "he", and substring("hamburger", 4, 8) should return "urge".

The call of substring("howdy", 3, 3) should return "" (an empty string). You should throw an IllegalArgumentException if the start index is negative or if the ending index is greater than the length of the string or if the start index is greater than the ending index.

In implementing this method, you are restricted to the following string methods: charAt, equals, and length. Do not write any loops in your code.

Exercise : writeSequence

Write a recursive method writeSequence that accepts an integer n as a parameter and prints a symmetric sequence of n numbers with descending integers ending in 1 followed by ascending integers beginning with 1, as in the following table:

Notice that for odd numbers the sequence has a single 1 in the middle while for even values it has two 1s in the middle. You should throw an IllegalArgumentException if passed a value less than 1. Do not write any loops in your code.

Exercise : stutter

Write a recursive method stutter that accepts a Stack of integers as a parameter and replaces every value in the stack with two occurrences of that value, in the same relative order. For example, if a stack named s stores the following values, your method will modify the stack as follows:

before: bottom [3, 7, 1, 14, 9] top
after : bottom [3, 3, 7, 7, 1, 1, 14, 14, 9, 9] top

Do not use any auxiliary data structures in your solution. Do not use loops; you must use recursion.

Exercise : evenDigits

Write a recursive method evenDigits that accepts an integer parameter n and that returns the integer formed by removing the odd digits from n. The following table shows several calls:

If a negative number with even digits is passed, the result should also be negative. Do not use any loops in your solution.