CODEWITHSUNDEEP
java
David
David

Reputation: 173

How is the recursion method adding itself?

Hello guys I have something that my brain is having a hard time trying to figure out. My homework is to have "x" bunnies. It recursively calculates the total number of bunny ears. The even numbered bunnies have the normal two ears, the odd numbered bunnies have 3 ears, but every 5th bunny has 1 ear. My code is complete and work... Here it is...

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;
     }
}

My question is, how in the world does the first number of ears accumulate to the second number of ears and so on? I was thinking naming a global variable for int y = 0; and then 

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);

I think this makes more sense because y is accumulating but it doesn't. Can you guys please explain how the other one accumulates and not y? THanks!

Upvotes: 1

Views: 2116

Answers (5)

Cruncher
Cruncher

Reputation: 7796

So for BunnyEars(5) let's trace it.

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

Note that none of the adding actually happens until the last BunnyEars call. Everytime it tries to add to the result of a recursive call it has to wait for the return, which will then call a new one etc. Then it works backwards returning to all of the methods adding the result along the way, before finally returning the result to the caller.

Upvotes: 4

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726899

I was thinking naming a global variable for int y = 0 and then

No, global variable should not be used there (although having a local variable could give you slightly more clarity):

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);

The trick to this (and any other) recursive function is realizing that there's more than one x. Since the function calls itself with a different argument, so each invocation has its own x.

Here is how the sequence of calls and returns looks:

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

Once you see that more than one call to BunnyEars is active at the same time, this should start to make sense: the chain of calls goes on without returning until it hits the x==0 "no bunny - no ears!" clause, at which point the chain starts to unroll, adding the proper number of ears to the return value of the previous invocation.

Upvotes: 5

tckmn
tckmn

Reputation: 59323

Here's your method:

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;
}

Here's a hypothetical example call:

BunnyEars(7)

This then becomes

return 3 + BunnyEars(6)

Which becomes

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

Suggested improvement to the code: Add a guard clause to the beginning:

if (x == 0) return 0;

Then you can remove all of the && x != 0s in the if statements. This will clean up the code a lot.

You also have lots of extraneous parenthesis - (x % 2) == 0 is the same as x % 2 == 0.

Improved code:

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);
}

Upvotes: 7

Noctua
Noctua

Reputation: 5218

I'll give another, easier, recursive example. Say we want the sum of all integer numbers up to n:

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

Let's call this function for n equals 0. Of course, the check succeeds, and we get 0 as return value.

Let's call this function for n equals 1. The check fails, so we return 1 plus the result of sumUpTo(0). We already know this results in 0, so the final result is 1. We could say the result is 1 + sumUpTo(1 - 1) = 1 + sumUpTo(0) = 1 + 0 = 1.

For 2, we get the call: 2 + sumUpTo(2 - 1) = 2 + sumUpTo(1) = ... = 3. And so on. The accumulation you desired is done on the fly.

Upvotes: 1

Jon Newmuis
Jon Newmuis

Reputation: 26520

Try breaking it down case-by-case.

Say you have no bunnies

BunnyEars(0) will return 0, because it doesn't go into any of the other cases.

Say you have one bunny

BunnyEars(1) will return 3 + BunnyEars(0), which we already know is 0. So it will evaluate to 3 + 0 which equals 3.

Say you have two bunnies

BunnyEars(2) will return 2 + BunnyEars(1), which we already know is 3. So it will evaluate to 2 + 3 which equals 5.

Continue with this pattern, and it should illustrate how to step through this logic recursively.

Upvotes: 1

Related Questions