algorithm - 如何解决给定算法的递归？

Question

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

我解决了这个问题，我得到了

T(n, m) = 1 + T(m, n%m)  if n > m
        = 1 + T(m, n)    if n < m
        = m              if n%m == 0

我很困惑如何进一步获得最终结果。请帮我解决这个问题。

Answer 1

这里的问题是 m 和 n 的下一个值的大小取决于之前的值，而不仅仅是它们的大小。Knuth 在“计算机编程的艺术”第 2 卷：半数值算法，第 4.5.3 节中对此进行了详细介绍。大约五页后，他证明了您可能已经猜到的内容，即最坏的情况是 m 和 n 是连续的斐波那契数。由此（或其他！）事实证明，在最坏的情况下，所需的除法次数在两个参数中较大的一个的对数中是线性的。

经过大量繁重的数学运算后，Knuth 证明了平均情况在参数的对数中也是线性的。

Answer 2

mcdowella对此给出了完美的答案。

对于直观的解释，您可以这样想，

如果 n >= m，n mod m < n/2；

这可以表示为，

如果 m < n/2，则： n mod m < m < n/2

如果 m > n/2，则： n mod m = nm < n/2

因此，您有效地将较大的输入减半，并且在两次调用中，两个参数都将减半。