Objectives

• Write a recursive function that computes a value.
• Use recursion to solve string and array problems.

Note: CodingBat is a free site of live problems to build skill in Java and/or Python. It was created by Nick Parlante, who is Computer Science lecturer at Stanford. If you create an account, CodingBat will automatically save your progress online.

Exercise 8.1   Math Functions

Many interesting functions in mathematics can be defined recursively. The good news is, recursive definitions are fairly easy to implement in Java! Download MathFunctions.java and implement the following functions:

• Exponentiation (x to the nth power). You may assume that n will not be negative.

  

• Binomial coefficient (n choose k). You may assume that n and k will not be negative.

  

• Ackermann function (recent discovery). You may assume that n and m will be 0 to 5.

  

Don't think too hard about these methods; each one should be less than 10 lines of code. After you get them working, step through your code using a debugger or Java Tutor to see how they work.

Exercise 8.2   Simple Counts

The rest of this homework is based on CodingBat problems. As explained on the Recursion-1 page, "first test for one or two base cases that are so simple, the answer can be returned immediately. Otherwise, make a recursive a call for a smaller case (that is, a case which is a step towards the base case). Assume that the recursive call works correctly, and fix up what it returns to make the answer."

• bunnyEars
• triangle
• sumDigits

Complete these problems online first, until you get them 100% correct. Then download the SimpleCounts.java source file and paste your code into the corresponding method stubs. Resolve any Checkstyle errors, and submit your final code to Autolab.

Exercise 8.3   Running Totals

These problems are a little bit more difficult, because they don't always add the same amount. If you use a variable to store how much to add, then you will only need one method call at the end. That way, you'll have two return statements: one for the base case, and one for the recursive case.

• count7
• count8
• bunnyEars2

Complete these problems online first, until you get them 100% correct. Then download the RunningTotals.java source file and paste your code into the corresponding method stubs. Resolve any Checkstyle errors, and submit your final code to Autolab.

Exercise 8.4   String Recursion

In the previous exercises, you made the problem smaller by decreasing the integer each time. With strings, you can make the problem smaller by using substring in the recursive call. Solve the problem for the first character only, and then recursively solve the rest of the problem.

• countHi
• allStar
• stringClean

Complete these problems online first, until you get them 100% correct. Then download the StringRecursion.java source file and paste your code into the corresponding method stubs. Resolve any Checkstyle errors, and submit your final code to Autolab.

Exercise 8.5   Array Recursion

CodingBat uses a different strategy for array problems than string problems. Rather than make the array smaller each time, you pass the current index as an argument. The index will be 0 the first time the method is called, and the base case is when you reach the end of the array.

• array6
• array11
• array220

Complete these problems online first, until you get them 100% correct. Then download the ArrayRecursion.java source file and paste your code into the corresponding method stubs. Resolve any Checkstyle errors, and submit your final code to Autolab.