RECURSION EXERCISES

READING 
-------
Sedgewick, 187-212

EXERCISES
---------

 1. Sedgewick, Exercise 5.3.

 2. Sedgewick, Exercise 5.6.

 3. Sedgewick, Exercise 5.8.

 4. Sedgewick, Exercise 5.14.

 5. Sedgewick, Exercise 5.17.

 6. Sedgewick, Exercise 5.29.

 7. Sedgewick, Exercise 5.30.

 8. Sedgewick, Exercise 5.33.

 9. Sedgewick, Exercise 5.39. Assume expressions are evaluated from
    left to right.  (In C, the order of evaluation is not specified.)




































.
.
.
.
		    ANSWERS TO RECURSION EXERCISES


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

 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.   eval() + * * 12 12 12 144
        eval() * * 12 12 12
          eval() * 12 12
            eval() 12
            eval() 12
            return 144 = 12*12
          eval 12
          return 1728 = 144*12
        eval 144
        return 1872 = 1728+144

 4.   link deletefinal(link x)
        {
          if (x == NULL) return NULL;
          if (x->next == NULL)
            { free(x); return NULL; }
          x->next = deletefinal(x->next);
          return x;
        }

 5.   int findmax(link x)
        { int a, b;
          if (x == NULL) return 0;
          a = x->item; b = findmax(x->next);
          if (a > b) return a; else return b;
        }

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

 7.   See Programming Assignment 6.

 8.   4^n

 9.
                      21
      
                8            13
      
           3         5     5    8
      
        1     2    2   3
      
            1   0