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
    addi == 0j
    fibn <= 1n

  2. ProcedureRecursive Call(s)
    factorialfactorial(n-1)
    sum1toNsum1toN(n-1)
    addadd(i-1, j+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)
    add(2,12)            2
                        12
                         -
    add(3,11)            3
                        11
                         -
    add(4,10)            4
                        10
                         -
    add(5,9)             5
                         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);
    }