More-of-the-input iterative algorithms extend a solution for a smaller input instance into a larger one. We will see in Chapter 9 that recursive algorithms do this too. The following is an amazing algorithm that does this. It finds the greatest common divisor (GCD) of two integers. For example, *GCD* (18, 12) = 6. It was first done by Euclid, an ancient Greek. Without the use of loop invariants, you would never be able to understand what the algorithm does; with their help, it is easy.

**Specifications:** An input instance consists of two positive integers, *a* and *b.* The output is *GCD*(*a, b*).

**The Loop Invariant:** Like many loop invariants, designing this one required creativity. The algorithm maintains two variables *x* and *y* whose ...

Start Free Trial

No credit card required