# 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);
}
}
```
Call Output
`mystery2(1);` 1
`mystery2(4);` 1, 2, 4
`mystery2(16);` 1, 2, 4, 8, 16
`mystery2(30);` 1, 3, 7, 15, 30
`mystery2(100);` 1, 3, 6, 12, 25, 50, 100

# 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);
}
}
```
Call Output
`mystery3(6)` 6
`mystery3(17)` 8
`mystery3(259)` 7
`mystery3(977)` 5
`mystery3(-479)` -2

# 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);
}
}
```
Call Output
`mystery6(4, 1);` 4
`mystery6(4, 2);` 8, 4, 8
`mystery6(8, 2);` 16, 8, 16
`mystery6(4, 3);` 12, 8, 4, 8, 12
`mystery6(3, 4);` 12, 9, 6, 3, 6, 9, 12

# 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:

Call Output
`writeChars(1);` `*`
`writeChars(2);` `**`
`writeChars(3);` `<*>`
`writeChars(4);` `<**>`
`writeChars(5);` `<<*>>`
`writeChars(6);` `<<**>>`
`writeChars(7);` `<<<*>>>`
`writeChars(8);` `<<<**>>>`

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:

Call Output
`writeSequence(1);` `1`
`writeSequence(2);` `1 1`
`writeSequence(3);` `2 1 2`
`writeSequence(4);` `2 1 1 2`
`writeSequence(5);` `3 2 1 2 3`
`writeSequence(6);` `3 2 1 1 2 3`
`writeSequence(7);` `4 3 2 1 2 3 4`
`writeSequence(8);` `4 3 2 1 1 2 3 4`

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:

Call Returns
`evenDigits(8342116)` `8426`
`evenDigits(4109)` `40`
`evenDigits(8)` `8`
`evenDigits(-34512)` `-42`
`evenDigits(-163505)` `-60`
`evenDigits(3052)` `2`
`evenDigits(7010496)` `46`
`evenDigits(35179)` `0`
`evenDigits(7)` `0`

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