## CS113 Lab 10: Recursion excursion

Due Thursday, December 1st, before midnight

Goals

• Practice writing recursive functions

## Recursive functions

In the file, `Recursion.java`, implement each of the following functions recursively. You are given basecode containing functions stubs along with a `main` for testing. You can download the basecode here or use the file in Dropbox.

 You must not modify the function parameters and return types for the given functions! BUT you can add additional functions. For example, when working with arrays, define a recursive function that takes an index (like the examples from class).
1. even numbers

Function `reven(int n)` should recursively sum the even numbers starting at 2 and ending at n. For example, `reven(10)` should return 2+4+6+8+10 = 30.

2. max of a list Function should recursively find the largest item in the list and return it. For example: the list `{5,20,-4,18}` has max of 20.

3. reverse a string

Function `rrevStr(String word)` should return the reverse of a given string. For example: the reverse of `"hello"` is `"olleh"`.

4. blastoff

Function ```rblastoff(int n)`should count down (print one number per line) from the given start number to 1, then print "blastoff!". For example, `rblastoff(10)``` should count down from 10 to 1, then print "blastoff!".

5. get integer divisible by 3

Function (`rgetMod()`) asks the user to enter an integer that is divisible by 3. Assume the user will enter an integer. If the given integer is not divisible by 3 (Hint: use `%` to check), the function should recursively ask the user for another integer. This function should return the valid integer. Below is console output from running `rgetMod`.

``````Enter a number: 4
Not divisible by 3!
Enter a number: 6``````
 `rgetMod` should return the user’s number!
6. xerox

Function (`rxerox(String phrase,int n)`) should generate and return a String containing `n` copies of the item. For example, `rxerox("paper", 4)` should return `"paperpaperpaperpaper"`, and `rxerox("2", 10)` should return `"2222222222"`.

7. raise to power

Function `rraise(int n, int m)` returns `n` raised to the mth power. For example, calling `rraise(6,2)` returns 36.

8. is palindrome?

Function `risPalindrome(String text)` returns `true` if given text is a palindrome (same forwards and backwards) and `false` otherwise. For example, `risPalindrome("HANNAH")` should return `true`.

9. Average of a list

Function `raverage(int[] L)` returns the average of a list of integers. Hint: implement this using a recursive function that computes the sum.

10. Max value in a list

Function `rmax(int[] L)` returns the max value of a list of integers.

11. Reverse a list

Function `rreverse(int[] L)` reverses the contents of a list inline (e.g. without creating a copy of the list)

12. count in String

Function `rcount(char x,String S)` returns how many times `x` is in the String `S`. For example, `rcount("a", "aardvark")` should return 3.

You are given test code in `main`. Functions that return a value are tested using the `test` function. This function throws an exception if the function returns an incorrect value. For example, suppose there is a bug in our function `rrevStr`, running gives this error

``````java.lang.Exception: Test Failed: yolleh != olleh
at Recursion.test(Recursion.java:118)
at Recursion.main(Recursion.java:133)``````

The above error shows us that our function returned "yolleh" but should have returned the value "olleh". We can also see that the function we need to fix is called on line 133.

We encourage you to add your own tests! When your program is free of errors, it will produce the following output.

``````\$ java RecursionSoln
5
4
3
2
1
blastoff
Enter an integer: 10
10 is not divisble by 3!
Enter an integer: -1
-1 is not divisble by 3!
Enter an integer: 22
22 is not divisble by 3!
Enter an integer: 33
SUCCESS: rgetMod 0.0 = 0.0
SUCCESS: reven 30.0 = 30.0
SUCCESS: reven 30.0 = 30.0
SUCCESS: reven 0.0 = 0.0
SUCCESS: rrevStr olleh = olleh
SUCCESS: rrevStr A = A
SUCCESS: rrevStr  =
SUCCESS: rrevStr HANNAH = HANNAH
SUCCESS: rxerox lalalala = lalalala
SUCCESS: rxerox  =
SUCCESS: rraise 8.0 = 8.0
SUCCESS: rraise 1.0 = 1.0
SUCCESS: risPalindrome true = true
SUCCESS: risPalindrome false = false
SUCCESS: risPalindrome true = true
SUCCESS: risPalindrome true = true
SUCCESS: risPalindrome true = true
SUCCESS: rcount 2.0 = 2.0
SUCCESS: rcount 0.0 = 0.0
SUCCESS: raverage 6.25 = 6.25
SUCCESS: raverage 0.0 = 0.0
SUCCESS: rmax 10.0 = 10.0
SUCCESS: rmax 10.0 = 10.0
SUCCESS: rmax 2.0 = 2.0
SUCCESS: rmax -1.0 = -1.0
SUCCESS: rreverse [8, 10, 5, 2] = [8, 10, 5, 2]
SUCCESS: rreverse [8, 5, 2] = [8, 5, 2]
SUCCESS: rreverse [] = []``````

## What to hand-in

1. The program, `Recursion.java`

1. Copy your files to your dropbox, into the folder called `A10`.