找到你要的答案

Q:Number of recursive calls in this algorithm

Q:此算法中的递归调用数

I have the following C code. I wanted to know how many recursive calls are made by this function?

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

The answer is O(log n) . In my view, it should be O(n) . Please explain how it is O(log n).

Thanks in advance.

我有以下C代码。我想知道这个函数有多少递归调用?

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

答案是O(log N)。在我看来,应该是O(N)。请解释它是如何O(log n)。

先谢谢了。

algorithm  recursion