Suppose I compute the GCD in a rather simple-minded recursive way: $$ \gcd(a, b) = \begin{cases} \gcd(a, b-a) & \text{ if }{a < b}, \\ \gcd(a-b, b) & \text{ if }{a > b}, \\ a & \text{ if } {a = b}. \end{cases} $$
In the worst-case scenario, this may take about $\max\{a,b\}$ steps - just put $a = 1$ and take large $b$. What I am curious about is the average case.
If $a,b$ are chosen uniformly at random from $[1,n]$, what can be said about the expected number of recursive steps?
(My main motivation is just idle curiousity.)