# Recursion: Solutions to Practice Problems

Ask if you are surprised by any of these answers.
1. ProcedureTermination ConditionBase Case Return Value
factorialn <= 11
sum1toNn < 10
fibn <= 1n

2. ProcedureRecursive Call(s)
factorialfactorial(n-1)
sum1toNsum1toN(n-1)
fibfib(n-1) and fib(n-2)

3. ```factorial(5)
5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1
120

Execution stack:
factorial(1)    n = 1
return = 1
factorial(2)    n = 2
return = -   (not yet assigned)
factorial(3)        3
-
factorial(4)        4
-
factorial(5)        5
-
```

4. ```sum1toN(5)
5 + sum1toN(4)
5 + 4 + sum1toN(3)
5 + 4 + 3 + sum1toN(2)
5 + 4 + 3 + 2 + sum1toN(1)
5 + 4 + 3 + 2 + 1 + sum1toN(0)
5 + 4 + 3 + 2 + 1 + 0
15
```

5. ```

Execution stack:
add(0,14)       i =  0
j = 14
return = 14
add(1,13)       i =  1
j = 13
return =  -   (not yet assigned)
12
-
11
-
10
-
9
-
```

6. ```double investmentValue(double investment, double interestRate, int years) {
if (years == 0)
return investment;
else
return investmentValue(investment * (1 + interestRate), interestRate, years-1);
}
```

7. ```double amountOwed(double loan, double interestRate, double payment, int months) {
if (months == 0)
return loan;
else
return amountOwed(loan * (1 + interestRate/12) - payment, interestRate, payment, months-1);
}
```

8. ```String duplicate(String s, int i) {
if (i == 0)
return "";
else
return s + duplicate(s, i-1);
}
```

9. ```String doubleSuccessively(String s, int i) {
if (i == 0)
return s;
else
return doubleSuccessively(s + s, i-1);
}
```