This is a text-only version of the following page on https://raymii.org:
---
Title : Euclid's algorithm: recursion and python
Author : Graham Morrison
Date : 08-03-2015
URL : https://raymii.org/s/articles/Euclids_algorithm_recursion_and_python.html
Format : Markdown/HTML
---
This article was originaly published in [Linux Voice, issue 1, April 2014][1].
This issue is now available under a [Creative Commons BY-SA license][2]. In a
nutshell: you can modify and share all content from the magazine (apart from
adverts), even for commercial purposes, providing you credit Linux Voice as the
original source, and retain the same license.
This remix is converted manually to Markdown and HTML for ease of archiving and
copy-pasting.
<p class="ad"> <b>Recently I removed all Google Ads from this site due to their invasive tracking, as well as Google Analytics. Please, if you found this content useful, consider a small donation using any of the options below:</b><br><br> <a href="https://leafnode.nl">I'm developing an open source monitoring app called Leaf Node Monitoring, for windows, linux & android. Go check it out!</a><br><br> <a href="https://github.com/sponsors/RaymiiOrg/">Consider sponsoring me on Github. It means the world to me if you show your appreciation and you'll help pay the server costs.</a><br><br> <a href="https://www.digitalocean.com/?refcode=7435ae6b8212">You can also sponsor me by getting a Digital Ocean VPS. With this referral link you'll get $100 credit for 60 days. </a><br><br> </p>
Other converted Linux Voice articles [can be found here][4].
* * *
Learn a wonderfully simple algorithm that teaches as much about Python as it
does about mathematics.
### Why do this?
* You'll learn ancient wisdom about numbers and their factors.
* This is a great way to see how Python deals with Boolean operations.
* While at the same time, see the danger of putting everything into one line.
We're about to go back to the year 300 BC. A time when much of the world looked
like the cover of the Led Zepplin album Houses of the Holy. This is the time of
Euclid; mathematician, Greek geek and founder of all things geometrical.
The problem that Euclid's algorithm solves is easy enough to understand: what is
the largest common divisor of two integers? Take the numbers 100 and 80, for
example: what's the largest number that divides into both?
You can make some assumptions about what that number might look like - it's
going to be even and less that 40, obviously, and maybe more than 20 - but to
get any closer is going to require a brute-force approach. Does 25 work? No. 30?
Nope. Looks like it might be 20 then, as this divides into both and it doesn't
look like there can be a higher number.
How about if the two numbers were 50 and 60? It's not obvious what the common
divisor might be for these two, which introduces more guesswork. Or what if the
numbers were 123456 and 654321?
### Adding and subtracting
For all the non-Euclids, the most basic algorithm may simply halve the smallest
number and then start counting down, checking whether the new number divides
into both.
It will work OK for small values, but it's obviously a computationally expensive
approach that will become unrealistic very quickly. There has to be a better
way, and that's where Euclid comes in.
Euclid discovered that if you compare the smaller number with the difference
between the smaller and the larger number, 50 compared to 10 in our second
example, and then carried on doing the same comparisons, smaller compared
against the remainder of the previous subtraction, until you could continue no
further, the previous remainder is the largest common divisor.
For the numbers 50 and 60, here's what happens:
* 60 - 50 = 10
* 50 - 10 = 40
* 40 - 10 = 30
* 30 - 10 = 20
* 20 - 10 = 10
* 10 - 10 = 0
So the largest common divisor between the numbers 50 and 60 is 10. Try it for
yourself. It may get a little longwinded - you could easily see that the
solution was going to be 10 in the previous example, for instance, but it always
works regardless of how big the numbers are you choose.
The next question we should be asking is, why? The solution is to do with common
divisors, the group of numbers that can be equally divided into both of our
values. The common divisor of a (assuming a is largest number in the pair), is
also a common divisor of a - b (assuming b is the second number).
In the first line of our previous calculation, that's the number 10 (60-50). 10
has its own set of devisors - 1,2, 5 and 10, and this process of subtraction
doesn't change the set of common divisors. This makes sense because when you
subtract the difference you are subtracting a number that shares the common
divisors of both numbers.
It might help if you think about this in terms of reversing the calculations
with addition:
10 + 10 = 20
20 shares the common divisors of 10, because we've just doubled it. 20 + 10 =
30.
Each addition sharing the same common factor that we started with, until... 50 +
10 = 60.
We now have our original two values, and you can see where the common divisors
came into the equation and how the reversal of this reveals them. The next job
is to put this idea into code, and you should be able to see that we're on the
verge of replacing our numbers with variables anyway, so we just need to add
some logic.
We're going to use Python for this example, as it's installed on virtually
everything - from the Raspberry Pi to Apple's OS X and your Linux distribution.
If you've not used the Python interpreter before, just type python on the
command line and make sure you follow our syntax and indentation exactly.
Here's the Python code:
def euclid(a, b):
return b and euclid(b, a%b)
Woah! Those two lines of code do what we've just spent 700 words trying to
explain! If this is your first foray into Python, we'll try to take it as slowly
as we can, starting off with what we've just created.
def euclid(a, b):
defines a function called euclid that takes two arguments: a and b. These values
are the same two values we were using before in our explanation. If you've just
typed this into Python, you can type `euclid(100,140)` to execute the function:
euclid(100,140)
The interpreter will spit out the answer, which in this case is 20.
Now let's look at what the function is doing, one word or character at a time.
`return` is how functions are halted when retuning results from an evaluation.
If this line were `return 1234`, the output from the function would always be
`1234`. But that doesn't include any evaluating, which in our example, is done
with the remainder of the line. The next character is `b`, our second number,
followed by the word `and`.
### Boolean operators
In programming terms, `and` is a Boolean operator. With most other programming
languages, for an evaluation to be true both sides of a Boolean and need to be
non-zero.
(1 and 1) is true, for example, whereas (0 and 1) is false, and those languages
would typically return a 1 for true and a 0 for false.
Python is slightly different in the way it handles return values because it
packs more features into a single operation. If the first value is non-zero, it
will return the second value from the evaluation.
If it's false, it will return the first. Here's a simple function definition and
the output from the interpreter to show you what we mean:
>>> def andtest(a,b):
... return a and b
...
>>> andtest(1,2)
2
>>> andltest(0,2)
0
This facility gives you the same output you get from other languages - if both
values are non-zero, you'll get a non-zero value returned, which is effectively
the same as (1 and 1) = true.
If either the first or the second values are zero, these will be returned,
effectively making (3 and 0) = false. But you get more because you get the value
of the second number for free, and this is how our code is working.
But there's another trick immediately afterwards - recursion:
euclid(b, a%b) or a
The second argument to the first and evaluation calls the function again from
within itself. That's the recursion part. The arguments for this second call of
the function are the second value itself and the remainder of a division between
the first and second number.
This remainder of a division, otherwise known as a modulo operation, is a
different method to the one we outlined earlier. It's the same theory, only made
more efficient.
This is because equal divisions of the lower number into the higher number -
such as 5 into 28 - help us to fast forward a few steps without losing the
common divisor.
28%5=3, which is because 28 divided by 5 = 5, with a remainder of 3. You get the
same result as the remainder from the subtractions we were doing earlier, only
without all the effort:
28 - 5 = 23 23 - 5 = 18 18 - 5 = 13 13 - 5 = 8 8 - 5 = 3
But when will this recursion stop? When will the function stop calling itself
and start returning values back up the chain? That's where the final `or a`
comes into play, and it's an evaluation connected to the earlier and statement.
In most programming languages, an or evaluation will only return true if one or
the other of the arguments is true - so (1 or 0) would equal true, but (0 or 0)
would be false. In Python, you get better value from the same statement because
it returns the first value if it's false and the second value if its not. Here's
another quick example from the interpreter:
>>> def ortest(a,b):
... return a or b
...
>>> ortest(1,2)
1
>>> ortest(0,2)
2
If the evaluation of the recursively embedded function returns zero, the `and`
evaluates the value of a against the value of b, effectively returning the next
to last value for b before the final evaluation returned 0.
That's exactly the same result we got when we first worked out Euclid's
algorithm manually, but it's quite difficult to imagine.
To make things clearer, here's some pseudo code for what happens when we call
the function with the values of 60 and 50, showing each recursive step on a line
with a number and the values Python is calculating. When a value is finally
returned, we change the line number with the returned value inserted into the
evaluation so you can see what's happening and how we step back through
recursion to the final number:
a = 60 b = 50
1: 60 and euclid(50, 10) or 60
2: 50 and euclid(10, 40) or 50
3: 40 and euclid(10, 30) or 40
4: 30 and euclid(10, 20) or 30
5: 20 and euclid(10, 10) or 20
6: 10 and euclid(10, 0) or 10 (RETURNS 10 )
5: 20 and 10 or 20 (RETURNS 10)
4: 30 and 10 or 30 (RETURNS 10)
3: 40 and 10 or 40 (RETURNS 10)
2: 50 and 10 or 50 (RETURNS 10)
1: 60 and 10 or 60 (RETURNS 10)
You can test the logic of that comparison yourself without the recursive
element:
>>> def eval(a,b,c):
... return a and b or c
...
>>> eval(20,10,20)
10
The end result is the product of thousands of years of thought - a concise
algorithm that performs a useful operation, all on a single line, while at the
same time teaching a little about how Python maximises functionality with its
Boolean operations (and also makes itself quite difficult to read in the
process).
[1]: http://www.linuxvoice.com/download-linux-voice-issue-1-with-audio/
[2]: https://creativecommons.org/licenses/by-sa/3.0/
[3]: https://www.digitalocean.com/?refcode=7435ae6b8212
[4]: https://raymii.org/s/tags/linux-voice.html
---
License:
All the text on this website is free as in freedom unless stated otherwise.
This means you can use it in any way you want, you can copy it, change it
the way you like and republish it, as long as you release the (modified)
content under the same license to give others the same freedoms you've got
and place my name and a link to this site with the article as source.
This site uses Google Analytics for statistics and Google Adwords for
advertisements. You are tracked and Google knows everything about you.
Use an adblocker like ublock-origin if you don't want it.
All the code on this website is licensed under the GNU GPL v3 license
unless already licensed under a license which does not allows this form
of licensing or if another license is stated on that page / in that software:
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
Just to be clear, the information on this website is for meant for educational
purposes and you use it at your own risk. I do not take responsibility if you
screw something up. Use common sense, do not 'rm -rf /' as root for example.
If you have any questions then do not hesitate to contact me.
See https://raymii.org/s/static/About.html for details.