c# - 递归乘法

Question

我正在关注这个 http://www.cs.berkeley.edu/~vazirani/algorithms/chap1.pdf (第 24 页底部)。在书中，作者描述了 Al Khwarizmi 乘法算法。这是我的实现

static int RecMultiply(int x, int y)
{
    if (y == 0)
        return 0;
    int z = RecMultiply(x, y / 2);
    if (y % 2 == 0)
        return 2 * z;
    else
        return x + 2 * z;
}

我已经多次检查代码，但我只是不理解它。为什么底部else将x加到2 * z？在我看来，z 在书中的算法中既用作总计又用作“右栏”数字。有人可以分解这段代码并解释一下吗？

Answer 1

由于乘法是简单的重复加法，如果 y 是对，您可以将它除以二，然后将 x 乘以二。 (所以，2*2 = 2+2。2*3 = 2+2+2、2*4 = 2+2+2+2 ....)
如果y是奇数，你可以减1，得到一个y是对，你需要加上一个x，(基本上， 1*y).

这是一个分割:

RecMultiply(5,5) :
+-  z = RecMultiply(5,2)
|   return 5 + 2 * z (=20 +5 =25)
|
|
+-- RecMultiply(5,2) :
    +-  z = RecMultiply(5,1)
    |   return 2 * z (=10)
    |
    +-- RecMultiply(5,1) :
        +-  z = RecMultiply(5,0)
        |   return 5 + 0
        |
        +---RecMultiply(5,0) :
            return 0

RecMultiply(5,4) :
+-  z = RecMultiply(5,2)
|   return 2 * z (=)
|
+-- RecMultiply(5,2) :
        +-  z = RecMultiply(5,1)
        |   return 2 * z (=10)
        |
        +-- RecMultiply(5,1) :
            +-  z = RecMultiply(5,0)
            |   return 5 + 0
            |
            +---RecMultiply(5,0) :
                return 0

所以，基本上，在递归位(处理所有对乘法)之后，您可能需要添加另一个 y，在上面的第一种情况下，它是 5 第一次调用)。

请注意 y=1 的特殊情况，这意味着 x*1 在我们的例子中显然是 5。同样的逻辑也适用。

如果有帮助，您可能想这样看:

static int RecMultiply(int x, int y)
{

    switch (y)
    {
        case 0:
            return 0;
            break;

        case 1:
            return x;
            break;

        default:
            return (y%2 ==0) ? RecMultiply(x, y/2)
                             : x + RecMultiply(x, y/2);
            break;
    } 
}

我认为它以更易于理解的方式表示 +1(或奇数情况)。