The complete recursive formula is: gcd(a,b)={agcd(b,amodb)if b=0otherwise This is the Euclidean algorithm, invented around 300 BCE. It is one of the oldest algorithms still used today.
Notice how each call swaps the arguments: a becomes b, and b becomes amodb. This is your first recursion with two changing parameters. Each recursive call brings you closer to the base case.