.
Recall that we are interested in computing the GCD of two non-negative integers: the largest number that divides both numbers evenly.
Euclid's algorithm computes the GCD of a and b by returning
a if b=0 and otherwise returning the GCD of b and .
Here is an animation to illustrate this process and also to help make it clear why it computes the correct answer.
