ANSWERS TO RECURSION EXERCISES


 1.     1
        2 1 
        3 10 5 16 8 4 2 1 
        4 2 1 
        5 16 8 4 2 1 
        6 3 10 5 16 8 4 2 1 
        7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
        8 4 2 1 
        9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 


 2.   gcd(89, 55)
        gcd(55, 34)
          gcd(34, 21)
            gcd(21, 13)
              gcd(13, 8)
                gcd(8, 5)
                  gcd(5, 3)
                    gcd(3, 2)
                      gcd(2, 1)
                        gcd(1, 0)


 3.   1 + 4 + 16 + 64 + 256 = 341

 4.   See the recursive graphics section of "Notes on Recursion."

 5.   4^n. This refers to the "Koch curve" in Sedgewick Figure 5.13.
      The "Koch snowflake" had 3 * 4^n segments.

 6.