Lab 23: Recursion

In this lab we will practice recursion.

Problem 0: Review

Review the following examples from the recursion lecture before you try these problems.

Problem 1: Exponentiation

Java provides a java.util.Math.pow(x,y) method to calculate the value of xy. Write a recursive version of the pow method that takes two integers as the arguments x and y. Use the following method header and implement the exponentiation operation recursively in Recursion.java:

    public static int powRec (int x, int y)

Test powRec by calling pow(2,3) and printing the result. You can use a main method in Recursion.java.

Problem 2: Largest element in an array

Write a recursive method that returns the largest element in an int array. This problem will use the following non-recursive function that calls the recursive function described below as a helper function:

  public static int largest(int[] aa) {
      return largestRec(aa, 1, aa[0]);
  }
Use the following method header and implement the helper function: largestRec. 
  public static int largestRec(int[] aa, int next, int largest)

Call largest in main to test largest by creating an array (a hardcoded array is okay). You can add all these methods in Recursion.java from Problem 1 above.

Problem 3: Reverse array

Write a method that recursively reverses the elements of an int array. This problem will use the following non-recursive function that calls the recursive function described below as a helper function: 

  public static void reverseArray(int[] aa) {
      reverseArrayRec(aa, 0, aa.length-1);
  }
Use the following method header and implement the reverse array operation recursively in the reverseArrayRec method in the same file that you used above, namely Recursion.java. 
  public static void reverseArrayRec(int[] aa, int from, int to)
Test reverseArray by creating two arrays (hardcoded is okay): one containing even number of elements and the other containing an odd number of elements, and then printing the arrays before and after a call to reverseArray.

More problems

When you reviewed Recur.java, you most likely recognized that there are some patterns in recursive functions. Try to review those patterns even though I have not added a problem for each of those patterns in this lab.

If you would like to try more problems, try some of the ones in Section 8.10 of our textbook, particularly if you have some time left at the end of today's lab session.

When you are done:

When you are done with these, feel free to leave the lab.