GCD - Walkthrough

Let me trace gcd($48$, $18$):

Call $1$: gcd($48$, $18$) $\rightarrow$ $48 \mod 18 = 12$, so call gcd($18$, $12$)

Call $2$: gcd($18$, $12$) $\rightarrow$ $18 \mod 12 = 6$, so call gcd($12$, $6$)

Call $3$: gcd($12$, $6$) $\rightarrow$ $12 \mod 6 = 0$, so call gcd($6$, $0$)

Call $4$: gcd($6$, $0$) hits base case ($b = 0$), returns $6$ The GCD of $48$ and $18$ is $6$. Notice how quickly the numbers shrink. This is why Euclid's algorithm is so efficient.