CSE 131 Module 2: Recursion

Practice Problems


Directions: Study the following recursive methods and answer the questions that follow. Do these practice exercises on paper. Do not type them into a computer. You'll learn more doing them by hand.
int factorial(int n) {
   if (n <= 1)
      return 1;
   else
      return (n * factorial(n-1));
}


int sum1toN(int n) {
   if (n < 1)
      return 0;
   else
      return (n + sum1toN(n-1));
}


int add(int i, int j) { // assumes i >= 0
   if (i == 0)
      return j;
   else
      return add(i-1, j+1);
}

int fib(int n) {  // assumes n >= 0
   if (n <= 1)
      return n;
   else
      return (fib(n-1) + fib(n-2));
}

  1. Identify the termination conditions (and resulting base case return values) in each of the above recursive methods.

  2. Identify the recursive calls in each of the above methods.

  3. Using the substitution model, show all the recursive calls and final result in the execution of factorial(5). For this same computation, draw the execution stack as it would look just before returning from factorial(1), the last recursive call.

  4. Using the substitution model, show all the recursive calls and final result in the execution of sum1toN(5).

  5. The data flow model is yet another way to illustrate a recursive computation. In the data flow model, you use boxes to represent method calls and arrows to represent the flow of information (parameters and return values). You can draw each recursive call as a black box with the parameters feeding in at the top left, and the return value coming out at the bottom left. To illustrate a method call, the parameters go out of the caller's right side and into the left side of the method being called. Return values go the other direction.

    Using the data flow model, show all the recursive calls and final result in the execution of add(5,9).

    For this same computation, draw the execution stack as it would look just before returning from add(0,14), the last recursive call.

  6. Using the data flow model, show all the recursive calls and final result in the execution of fib(5). (Try to do this without looking at the lecture notes.)

  7. Write a recursive method that takes as parameters an initial investment amount, an annual interest rate, and a number of years. The method should return the value of the investment after the given number of years, assuming that the interest is compounded annually. (For example, if the initial investment is 1000 and the interest rate is 10 percent, then after one year the investment will be worth 1100, after two years 1210, after three years 1331, etc.)

  8. Write a recursive method that takes as parameters an initial loan amount, an annual interest rate, a monthly payment, and a number of months. The method should return the amount that is still owed after the given number of months, assuming that the interest is compounded monthly. (That is, each month 1/12 of the annual interest rate is charged and the monthly payment is subtracted from the loan amount.)

  9. Write a recursive method that takes as parameters a String s and an integer i and returns a String that has s repeated i times. For example, if the given string is "Go bears! " and the integer is 3 then the return value would be "Go bears! Go bears! Go bears! ". (Note that if the integer is 0, then the empty string "" should be returned.)

  10. Write a recursive method that takes as parameters a String s and an integer i and returns a String that has s repeated 2^i times. For example, if the given string is "Go bears! " and the integer is 3 then the return value would be "Go bears! Go bears! Go bears! Go bears! Go bears! Go bears! Go bears! Go bears!". Do not use multiplication or exponentiation in your algorithm. Just double the length of the string i times.

Solutions