1

大家好，我有一些我的大脑很难弄清楚的事情。我的作业是养“x”个兔子。它递归地计算兔子耳朵的总数。偶数的兔子有正常的两只耳朵，奇数的兔子有3只耳朵，但每5只兔子就有1只耳朵。我的代码是完整的并且可以工作......在这里......

import java.util.*;

public class bunnies
{
    public static int y;

    public static void main(String[] args)
    {
        y = 0;
        System.out.println(BunnyEars(3));
    }

    public static int BunnyEars(int x)
    {
        if ((x % 5) == 0 && x != 1  && x != 0)
            return 1 + BunnyEars(x - 1);
        else if ((x % 2) == 0 && x != 0 )
            return 2 + BunnyEars(x - 1);
        else if ((x % 2) != 0 && x != 0)
            return 3 + BunnyEars(x - 1);
        else
            return 0;
     }
}

我的问题是，世界上第一个耳朵如何累积到第二个耳朵等等？我正在考虑为 int y = 0; 命名一个全局变量；接着

if ((x % 5) == 0 && x != 1  && x != 0)
    y += 1;
else if ((x % 2) == 0 && x != 0 )
    y += 2;
else if ((x % 2) != 0 && x != 0)
    y += 3;
else
    return 0;
return y + BunnyEars(x -1);

我认为这更有意义，因为 y 正在积累，但事实并非如此。你们能解释一下另一个是如何累积的而不是y吗？谢谢！

4

5 回答 5

7

这是你的方法：

public static int BunnyEars(int x)
{
    if ((x % 5) == 0 && x != 1  && x != 0)
        return 1 + BunnyEars(x - 1);
    else if ((x % 2) == 0 && x != 0 )
        return 2 + BunnyEars(x - 1);
    else if ((x % 2) != 0 && x != 0
            )
        return 3 + BunnyEars(x - 1);
    else
        return 0;
}

这是一个假设的示例调用：

BunnyEars(7)

这然后变成

return 3 + BunnyEars(6)

变成

return 3 + 2 + BunnyEars(5)
return 3 + 2 + 1 + BunnyEars(4)
return 3 + 2 + 1 + 2 + BunnyEars(3)
return 3 + 2 + 1 + 2 + 3 + BunnyEars(2)
return 3 + 2 + 1 + 2 + 3 + 2 + 3 + BunnyEars(0)
return 3 + 2 + 1 + 2 + 3 + 2 + 3 + 0
return 16

对代码的建议改进：在开头添加一个保护子句：

if (x == 0) return 0;

然后您可以删除语句&& x != 0中的所有 s 。if这将清理代码很多。

您还有很多多余的括号 -(x % 2) == 0与x % 2 == 0.

改进的代码：

public static int BunnyEars(int x)
{
    if (x < 0) throw new IllegalArgumentException("Bunnies cannot be negative"); // handle bad input
    if (x == 0) return 0;
    if (x % 5 == 0) // no need for `&& x != 1` because 1 % 5 isn't 0 anyway
        return 1 + BunnyEars(x - 1);
    else if (x % 2 == 0)
        return 2 + BunnyEars(x - 1);
    else if (x % 2 != 0)
        return 3 + BunnyEars(x - 1);
}
于 2013-09-17T20:50:01.750 回答
5

int y = 0我在想为然后命名一个全局变量

不，不应该在那里使用全局变量（尽管有一个局部变量可以让你更清楚一些）：

if (x == 0) return 0; // Zero bunnies --> zero ears
int y = 0; // Variable y represents the number of ears that bunny number x has
if ((x % 5) == 0 && x != 1  && x != 0)
    y = 1;
else if ((x % 2) == 0 && x != 0 )
    y = 2;
else if ((x % 2) != 0 && x != 0)
    y = 3;
return y + BunnyEars(x -1);

这个（和任何其他）递归函数的诀窍是意识到有不止一个x. 由于函数使用不同的参数调用自身，因此每个调用都有自己的x.

以下是调用和返回序列的外观：

BunnyEars(x==6)
    Compute y for x==6 // That's 2
    Call BunnyEars(x==5)
        Compute y for x==5 // That's 1
        Call BunnyEars(x==4)
            Compute y for x==4 // That's 2
            Call BunnyEars(x==3)
                 Compute y for x==3 // That's 3
                 Call BunnyEars(x==2)
                     Compute y for x==2 // That's 2
                     Call BunnyEars(x==1)
                         Compute y for x==1
                         Call BunnyEars(x==0)
                         return 0 // Zero bunnies --> zero ears
                     return 2+0 --> 2
                 return 3+2 --> 5
             return 2+5 --> 7
         return 1+7 --> 8
     return 2+8 --> 10

一旦您看到多个呼叫同时BunnyEars处于活动状态，这应该开始有意义：呼叫链继续进行而没有返回，直到它击中x==0“没有兔子 - 没有耳朵！” 子句，此时链开始展开，将适当数量的耳朵添加到前一次调用的返回值中。

于 2013-09-17T20:55:06.627 回答
4

所以对于 BunnyEars(5)，让我们追踪它。

BunnyEars(5)
1 + BunnyEars(4)
1 + 2 + BunnyEars(3)
1 + 2 + 3 + BunnyEars(2)
1 + 2 + 3 + 2 + BunnyEars(1)
1 + 2 + 3 + 2 + 3 + BunnyEars(0)
1 + 2 + 3 + 2 + 3 + 0

请注意，在最后一次 BunnyEars 调用之前，实际上不会发生任何添加。每次尝试添加到递归调用的结果时，它都必须等待返回，然后返回调用一个新的，等等。然后它向后工作，返回所有添加结果的方法，最后返回结果给调用者。

于 2013-09-17T20:48:47.477 回答
1

尝试逐案分解。

说你没有兔子

BunnyEars(0)将返回0，因为它不会进入任何其他情况。

假设你有一只兔子

BunnyEars(1)将返回3 + BunnyEars(0)，我们已经知道是0。所以它将评估为3 + 0which equals 3。

假设你有两只兔子

BunnyEars(2)将返回2 + BunnyEars(1)，我们已经知道是3。所以它将评估为2 + 3which equals 5。

继续这个模式，它应该说明如何递归地遍历这个逻辑。

于 2013-09-17T20:49:45.537 回答
1

我将给出另一个更简单的递归示例。假设我们想要直到 n 的所有整数的总和：

public static int sumUpTo(int n) {
    if(n == 0) return 0;
    return n + sumUpTo(n - 1);
}

让我们调用这个函数，因为 n 等于 0。当然，检查成功，我们得到 0 作为返回值。

让我们调用这个函数，因为 n 等于 1。检查失败，所以我们返回 1 加上 的结果sumUpTo(0)。我们已经知道结果是 0，所以最终结果是 1。我们可以说结果是1 + sumUpTo(1 - 1) = 1 + sumUpTo(0) = 1 + 0 = 1。

对于 2，我们接到电话：2 + sumUpTo(2 - 1) = 2 + sumUpTo(1) = ... = 3. 等等。您想要的积累是即时完成的。

于 2013-09-17T20:52:26.720 回答