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.

Testing your functions

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

  2. Make sure your programs have a header containing your name, date, and description.

  3. No writeup is necessary for this assignment

How to hand-in

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