When does the recursion stop? When . At that point, . Any number divides (since for any ), so the GCD of and is just itself.
This is your base case. Every recursive call reduces (since ), so you will always reach eventually. This is where recursion stops. Without it, you get infinite recursion and a stack overflow. Every recursive solution needs at least one base case.