I was rereading Paul Ford's amazing essay "What Is Code?" yesterday when it mentioned Euclid's algorithm, one of the oldest algorithms still commonly in use today. It is a way to find the GCD of two numbers (greatest common divisor) and it does it like so:
1. Take 2 numbers
2. The greater number modulo the smaller number equals the remainder
3. If the remainder is not 0, the smaller number becomes the new greater number and remainder becomes the new smaller number
4. Do steps 1 - 3 for as many times as you need to in order to get a remainder that is equal to 0
5. At that point, return the most recent smaller number.
I appreciated the recursive nature of this lovely little algorithm and decided to try it out and practice my recursion skills, all at the same time:
It can still be shortened, but it's short enough and simple enough already so why make it complicated by trying to oversimplify? The only issue I ran into was that I wasn't clear on which number I was supposed to return, but after rewatching this visual tutorial everything eventually clicked for me.