Euclid's GCD with recursion
Find the greatest common divisor (HCF) of two numbers with a function that calls itself: gcd(a, b) calls gcd(b, a % b), and the numbers shrink until the remainder is 0. Watch the call stack, count the calls, and see which pairs share no divisor but 1.
Core concept
Euclid's rule gcd(a, b) = gcd(b, a % b) makes the numbers smaller at every call, so a recursive function reaches its base case, b = 0, where the answer is a
Topic: Functions and recursion
The greatest common divisor (GCD), also called the HCF, of two numbers is the biggest number that divides both. More than two thousand years ago Euclid found a quick way: the GCD of a and b is the same as the GCD of b and the remainder a % b. So gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0). When the second number is 0, the answer is the first number: here 6. That makes a neat recursive function. gcd(a, b) has a base case, IF b == 0 THEN RETURN a, and otherwise it returns gcd(b, a % b). Each call has its own a and b, and because the remainder is always smaller than b, the numbers shrink and the calls must stop.
What you will learn
- Use the remainder % to apply Euclid's rule.
- Write a recursive function with a base case and a smaller recursive call.
- Trace the calls and their arguments on the call stack.
- Predict the GCD of two numbers and the number of calls.
Before you start
- Know how a function takes parameters and returns a value, and what a remainder is.
Materials
- A notebook to write each call
Equipment
- None
Procedure
- Run gcd(48, 18) and read the answer and the number of calls.
- Step through it and watch the arguments shrink.
- Try 17 and 13, which share no divisor but 1.
- Answer the practice challenges.