Java - 欧几里得算法的递归函数

Question

我似乎无法成功地将以下算法转换为Java代码，请原谅可怕的图片质量，因为我正在处理一个问题:

我尝试使用以下代码来表示欧几里得算法，但它似乎不起作用。 我真的不知道如何在Java代码中表示它。 有什么帮助吗?

public static int gcd(int x, int y) {
    if (y == 0) {
        return x;
    } else if (x >= y && y > 0) {
        return gcd(y, (x % y));
    }
}

感谢您的选择。

- mino

---

你正在正确地遵循教科书算法。只是教科书算法不完整 - 它没有考虑到既不满足任何一类的情况。 - Mysticial

它为什么不工作？当您调用它时，实际上会发生什么？您传递了哪些参数，它返回了什么？ - Keith Thompson

@KeithThompson 我相信 OP 目前的问题是代码无法编译。 - Sergey Kalinichenko

@dasblinkenlight：啊，非常正确。原帖作者仍然应该提到这一点，而不是说“但似乎不起作用”。 - Keith Thompson

Answer 1

x和y之间不存在任意顺序。

- 勿绮语

---

你所需要的仅是return y == 0 ? x : gcd(y,x%y);。无论哪个数大都没关系。但这会使递归多一次。 - st0le

FYI：此答案之前更有帮助（请参见编辑历史记录）。 - Brent Bradburn

Answer 2

您的代码还不完整！

如果 x < y呢？那么你的代码将不会返回任何值！

这本书没有提到的是，函数的两个参数不一定需要按降序排列（即x >= y）。您需要考虑这个事实来计算gcd。

简单地说，您可以执行以下操作：

public static int gcd ( int x , int y )
{
    if ( y == 0 )                        
        return x;
    else if ( x >= y && y > 0)
        return gcd ( y , x % y );
    else return gcd ( y , x );        // if x < y then go ahead and switch them around.
}

- Kaushik Shankar

Answer 3

你离成功已经很接近了。需要考虑当y > x时会发生什么，并从最终的else分支返回结果（提示：可以自由交换x和y的位置）。

- Sergey Kalinichenko

Answer 4

你已经接近成功了。

你的代码无法编译，因为没有一个“捕获所有”子句从函数返回。

这取决于你是否打算将负值y传递到此函数中。如果你只期望正值，则只需抛出异常。

public static int gcd(int x, int y) {

    if (y == 0) {

        return x;

    } else if (x >= y && y > 0) {

        return gcd(y, (x % y));

    }

    throw
        new IllegalArgumentException(
            String.format(
                "Unexpected values for x(%d) and y(%d)",
                Integer.valueOf( x ),
                Integer.valueOf( y )
            )
        );
}

- Alexander Pogrebnyak

---

理想情况下，我希望包括负值。 - mino

@m92 该作业中的递归公式不包括负数。 - Sergey Kalinichenko

Answer 5

这是我考虑到负数的代码：

public static int gcd(int x, int y)
{
    if (y == 0)
        return x;
    if (x < 0)
        return gcd(x * -1, y); //turns the first parameter to a positive if it's initally negative
    if (y < 0)
        return gcd(x, y * -1); //turns the second parameter to a positive if it's initally negative
    if (y <= x && x % y == 0)
        return y;

    return gcd(y, x%y);
}

注意，如果你想找到负数的最大公约数，并且其中一个数是负数，你可以将其变成正数，结果仍然相同。

如果两个数都是负数，那么我不确定最大公约数应该是什么。1？-1？我不知道，所以我没有考虑这种情况。我编写的代码只是将它们视为两个正数。

- Sean Rogers