How many recursive calls are made by this gcd function? In the following function, let $n \geq m$.  

int gcd(n,m)  
{  
 if (n % m == 0) return m;  
 n = n % m;  
 return gcd(m, n);  
}


How many recursive calls are made by this function?


$\Theta (\log_2 n)$
$\Omega (n)$
$\Theta (\log_2(\log_2 n))$
$\Theta ( \sqrt{n} )$  


I think the answer is $\Theta (\log_2(\log_2n))$, but my book is saying $\Theta (\log_2 n)$.    

My reasoning is as follows. Here we are not dividing the number. If there was a division then it would be $\log n$. But here operation is $\bmod$. So we will get a very small number after the first call. So it must be $\log \log n$. Am I thinking correctly?
Hint: on input $F_{n+1},F_n$, gcd makes a recursive call with inputs $F_n,F_{n-1}$. Now use the asymptotic formula $F_n = \phi^n + \Theta(1)$, where $\phi = (1+\sqrt{5})/2 &gt; 1$.

Also, while we're at it, $\Theta(\log_2 n) = \Theta(\log n)$, and similarly $O(\log_2 n) = O(\log n)$ (and the same fore $\log\log n$); try to figure out why (here the base of $\log n$ can be arbitrary, but for definiteness you can choose base $e$).