## 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
}

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.