PPP Exercises: Recursive Programming

Exercise: Greatest common divisor

Write a function 'gcd' that implements the following definition of the greatest common devisor:

gcd(n = m) = n
gcd(n < m) = gcd(n {m-n})
gcd(n > m) = gcd({n-m} m)

Test the function with:

gcd(10 8);
gcd(10 11);
gcd(11 10);

Exercise: Towers of Hanoi

Move n disks of different size from one post to another using a third post without placing a larger disk on a smaller one. At the beginning all n disks are placed on one peg, the largest at the bottom and the smallest at the top.

   |          |          |              |          |          |     
  -|-         |          |              |          |         -|-   
 --|--        |          |     ==>      |          |        --|--  
===+===    ===+===    ===+===        ===+===    ===+===    ===+===
Of course everybody of you knows the adequate algorithm, yet to save some time to those who don't quite remember it, here it is again:

To move n disks from a post A to a post C via B, do as follows:

  1. If n is 1, then move it from A to C.
  2. If n is not 1, then move n-1 disks from A to B, using this algorithm. Then move the remaining disk from A to C. Finally move the n-1 disks from B to C, again using this algorithm.
Ulrike Steffens, 1994