Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
The moose likes Beginning Java and the fly likes recurrsion explanation needed Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of Java Interview Guide this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "recurrsion explanation needed" Watch "recurrsion explanation needed" New topic

recurrsion explanation needed

Rauhl Roy
Ranch Hand

Joined: Aug 01, 2006
Posts: 401

may i know how the below recussion is working properly

it is giving properly..

but i dont know how this is being executed.
Rob Spoor

Joined: Oct 27, 2005
Posts: 20279

Lets take the 5 as an example:
bunnyEars(5) returns 2 + bunnyEars(4)
bunnyEars(4) returns 2 + bunnyEars(3)
bunnyEars(3) returns 2 + bunnyEars(2)
bunnyEars(2) returns 2 + bunnyEars(1)
bunnyEars(1) returns 2 + bunnyEars(0)
bunnyEars(0) returns 0 because this is specified as such

So if you put this together:
bunnyEars(5) returns 2 + (2 + (2 + (2 + (2 + 0))))

How To Ask Questions How To Answer Questions
marc weber

Joined: Aug 31, 2004
Posts: 11343

Although they're not needed, some additional braces and an "else" might make this more clear...

So when the number of bunnies reaches zero, then return zero. Otherwise:
  • Reduce the number of bunnies by 1. (So -- assuming that the initial int value is non-negative -- this will eventually get to zero so the method will stop making recursive calls).
  • Pass this reduced value back into the method (recursive call).
  • Add 2 to the value returned by the method.
  • Return this sum.
  • In other words, for each bunny (from the initial number of bunnies down to zero), add 2 ears to a cummulative sum. When you're done counting down, return this sum.

    "We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
    Anuradha Karunamuni
    Ranch Hand

    Joined: Dec 08, 2007
    Posts: 64
    First you give a value for the int variable bunnies when the bunnyEars() method is called. Then inside the method it checks if the value of bunnies is zero. If it is zero, then returns the values zero, giving the number of bunnyEars as zero (Obviously if the number of bunnies is zero, how can there be any ears). With this the method returns.

    If the bunnies is not equals to zero, return the value corresponding to the
    following statement;

    2 + bunnyEars(bunnies-1)

    Let's analyze this with an example. Lets say the number of bunnies=5.
    Then the method does not return zero, instead it returns the above value.

    2 + bunnyEars(bunnies-1) can be written as 2 + bunnyEars(4) since initially bunnies=5. Then bunnyEars() method is called again within the same method itself for the value bunnies=4. This goes on as follows;

    bunnyEars(5) = 2 + bunnyEars(4) ------- [A]
    bunnyEars(4) = 2 + bunnyEars(3) ------- [B]
    bunnyEars(3) = 2 + bunnyEars(2) ------- [C]
    bunnyEars(2) = 2 + bunnyEars(1) ------- [D]
    bunnyEars(1) = 2 + bunnyEars(0) ------- [E]

    When you substitute [B], [C], [D], [E] in to [A], you get the value 10 for number of ears.
    The process can be analyzed as above for any number of bunnies.

    What happens here is, the method calls itself while reducing the number of bunnies of which the ears need to be counted and adding 2 for each bunny reduced for the number of ears.

    Since here number of bunnies cannot be less than zero, it's better if you replace if (bunnies==0) with if (bunnies<=0).

    Put a reply if any further explanation is needed.

    "Simplicity is the ultimate sophistication..." ~Leonardo da Vinci~
    SCJP 1.4
    Rob Spoor

    Joined: Oct 27, 2005
    Posts: 20279

    Calling bunnyEars with a negative value will end:
    - the bunny parameter will be decreased until it becomes Integer.MIN_VALUE
    - another decrease will make it Integer.MAX_VALUE
    - it will be decreased further until it becomes 0

    However, the check could be better. Perhaps as follows:

    All depending on what you actually want bunnyEars to calculate
    marc weber

    Joined: Aug 31, 2004
    Posts: 11343

    Originally posted by Rob Prime:
    Calling bunnyEars with a negative value will end...

    Good point.
    Anuradha Karunamuni
    Ranch Hand

    Joined: Dec 08, 2007
    Posts: 64
    Sorry guys...My mistake ...(bunnies<=0) should be replaced with (bunnies>=0)...
    Or else follow Rob's method, it seems more practical.

    Sorry again...
    wood burning stoves
    subject: recurrsion explanation needed
    It's not a secret anymore!