Worst case will arise when both n and m are consecutive Fibonacci numbers.
gcd(Fn,Fn-1)=gcd(Fn-1,Fn-2)=?=gcd(F1,F0)=1 and nth Fibonacci number is 1.618^n, where 1.618 is the Golden ratio.
So, to find gcd(n,m), number of recursive calls will be T(logn).