Why does the Euclidean algorithm always terminate? Why does the Euclidean algorithm always terminate? Can we make this effective by bounding the number of steps it takes in terms of the original integers?
It always terminates because at each step one of the two arguments to $\gcd({}\mathbin\cdot{},{}\mathbin\cdot{})$ gets smaller, and at the next step the other one gets smaller.  You can't keep getting smaller positive integers forever; that is the "well ordering" of the natural numbers.  As long as neither of the two arguments is $0$ you can take it one more step, but it can't go on forever, so you have to reach a  point where one of them is $0$, and then it stops.

As for bounds, a very crude and easily established upper bound on the number of steps is the sum of the two arguments. One of the arguments is reduced by at least $1$ at each step, and you can't reduce $n$ repeatedly by $1$ more than $n$ times without bringing it to $0$.

The worst case is $\gcd(m,n)$ where the ratio of $m$ to $n$ is the ratio of two consecutive Fibonacci numbers.  For now I'll leave the proof of that as an exercise.
If you take gcd (x,0), the process doesn't terminate. In effect because r=x

This causes quite the show if you're using a physical adding machine

https://www.alltechbuzz.net/mechanical-calculator-dividing-by-zero/

(Link shows adding machine stuck in an endless loop)

So if the process never ends, you would conclude one of the integers in the Euclidean Algorithm would have to be 0.