We can think of the GCD algorithm as taking place inside a directed graph. The vertices of the graph are all pairs $(a,b)$, where $a,b \geq 0$. If $a \neq 0$, then there is an edge from $(a,b)$ to $(b \bmod a, a)$. The algorithm starts at some vertex $(a,b)$, follows the unique outgoing edges, until (hopefully) reaching a leaf $(0,b)$, at which point it outputs $b$.
We can consider a more general situation, in which we are given a directed graph in which every vertex has at most one outgoing edge, and a starting vertex. We start at that vertex, and follow the unique outgoing edges, stopping if we ever reach a leaf. In this generality, we cannot be certain that the process always terminates. In fact, if the graph contains a directed cycle and we start with a vertex on the cycle, the process will ever terminate!
Consider for example the graph on $1,2,3$ with edges $1\to 2$, $2 \to 3$, $3 \to
1$. On this graph, the iterative process will never terminate.
There is another reason for the process to not terminate: there might be an infinite directed path. For example, consider the directed graph on the integers in which the edges are $a \to a+1$. This graph contains no cycles, but nevertheless the process does not terminate.
To show that the GCD algorithm always terminates, we define a potential function $\phi$ on the vertices by $\phi(a,b) = a$. If $(a,b) \to (b \bmod a,a)$ then
$$
\phi(b \bmod a,a) = b \bmod a < a = \phi(a,b).
$$
Therefore the potential decreases. Since the potential is always a natural number, and these are well-ordered, it cannot decrease forever, and therefore the algorithm necessarily terminates.
To finish, let me mention the Collatz conjecture. Consider the directed graph on the positive integers in which the edges are $2n \to n$ and $2n+1 \to 3n+2$ for all $n \geq 1$. The Collatz conjecture states that the process considered above always terminates, no matter what the starting vertex is. The conjecture is suspected to be true, but nobody knows how to prove it.
