递归方法如何自我添加？

Question

大家好,我有一些东西,我的大脑很难弄清楚.我的作业是拥有"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？谢谢!

Answer 1

这是你的方法:

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 != 0s 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);
}

Answer 2

我想命名一个全局变量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"没有兔子 - 没有耳朵!" 子句,此时链开始展开,将适当数量的耳朵添加到前一次调用的返回值.