1.5 · Problem reduction

Replace the problem with a smaller equivalent one.

Euclid’s algorithm preserves the common divisors of two integers while replacing the larger problem with a remainder pair that quickly becomes smaller.

Guiding question

Why does replacing a and b with b and the remainder preserve their greatest common divisor?

Read remainder as the next problem state
Identify the common-divisor invariant across calls
Follow an exact integer process to its zero base case
Compare the shrinking call sequence with the final answer

If a number divides both a and b, it also divides the remainder after a is divided by b. The reverse direction holds as well, so the pair changes while its greatest common divisor does not.

Each call replaces (a, b) with (b, remainder(a, b)). When the second value reaches zero, the first value is the preserved greatest common divisor. No postponed arithmetic remains after the recursive call.

Lispex · SICP sourceScheme-compatible SICP syntax executed by the Lispex SICP profile.

(begin
  (define (euclid a b)
    (if (= b 0)
        a
        (euclid b (remainder a b))))
  (euclid 206 40))

Lispex learning runtimeLispex SICP profile 1.0.0

Loading Lispex SICP runtime

Lispex · SICP source111 / 1,048,576 UTF-8 bytes

Examples

Result—

Output: —
Value: —
Diagnostic: —

Visible execution0 / 0 trace events

This browser result is not a Lispex Vouch record or authority.wasm —

Expected observation

The first program returns 2. The second returns 21.

Trace focus

Follow (206, 40), (40, 6), (6, 4), (4, 2), and (2, 0). The second argument strictly shrinks until the base case exposes the invariant answer.

Try it yourself

Change the program before you read the hint.

Run euclid with 1999 and 97. Write every argument pair before revealing the final greatest common divisor.

Show one hint

Apply remainder to the current pair and move the old second value into the first position.