How is the recursion method adding itself?

Question

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!

" naming a global variable for int y = 0;" Java has no globals. Static may not be the best idea here. Recursive methods *pass everything the next call would need* in. — nanofarad, Sep 17 '13 at 20:47
If your assignment is specifically to use recursion, you shouldn't use a "global" variable. — James Montagne, Sep 17 '13 at 20:47
@hexafraction I think by "global" he means a class variable. — Dennis Meng, Sep 17 '13 at 20:48
http://stackoverflow.com/questions/18090465/recursion-in-c-factorial-program/18090513#18090513 — JNL, Sep 17 '13 at 20:50
In the first if statement, it is not necessary to check for x != 1 because in order to execute that test, (x % 5) == 0 must be true, which means x != 1. — fred02138, Sep 17 '13 at 20:52
@DavidCamacho Try out what you want to do for `x = 2`. The correct answer is 5, but your second program will return 7. — Dennis Meng, Sep 17 '13 at 20:52
"My code is complete and work" -- so, you wrote this program, and now you're asking us how it works? Why don't you just ask the person who did your homework for you to explain it to you? Also, if x is divisible by 5, it cannot be equal to 1. — David Conrad, Sep 17 '13 at 21:56

tckmn · Answer 1 · 2013-09-17T20:55:40.443

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

It's really one of those things, after he reads it 5 times it'll make perfect sense. — Cruncher, Sep 17 '13 at 20:54
So when we get to the last part "return 0;" it won't return 0 it will return 16 + 0? — David, Sep 17 '13 at 21:39
@DavidCamacho Well, it returns `0` **to the last iteration that called it**, so the `0` is summed with the total value. `return 3 + 2 + 1 + 2 + 3 + 2 + 3 + BunnyEars(0)` becomes `return 3 + 2 + 1 + 2 + 3 + 2 + 3 + 0`. — tckmn, Sep 17 '13 at 21:40
@DavidCamacho It's so confusing, and then suddenly it all makes sense at once :) You're welcome! — tckmn, Sep 17 '13 at 21:44

Sergey Kalinichenko · Answer 2 · 2013-09-17T21:01:06.323

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.

Cruncher · Answer 3 · 2013-09-18T13:07:48.537

4

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.

edited Sep 18 '13 at 13:07

answered Sep 17 '13 at 20:48

Cruncher

7,641
1
31
65

And, does that answer the question fully? – nanofarad Sep 17 '13 at 20:49
1

@hexafraction seeing how it executes is the best way to demonstrate recursion. You can see the accumulation here. – Cruncher Sep 17 '13 at 20:49
1

@hexafraction the answer that got an upvote was the same as mine, except they pasted his method in. – Cruncher Sep 17 '13 at 20:51
2

It's minor, but technically, that last step should have a `BunnyEars(0)` at the end. – James Montagne Sep 17 '13 at 20:59
@JamesMontagne yeah, my brain kind of filters out the base cases – Cruncher Sep 18 '13 at 13:08

score 1 · Answer 4 · answered Sep 17 '13 at 20:49

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.

score 1 · Answer 5 · answered Sep 17 '13 at 20:52

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.

How is the recursion method adding itself?

5 Answers5