• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

recurrsion explanation needed

 
Rauhl Roy
Ranch Hand
Posts: 401
Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
may i know how the below recussion is working properly



it is giving properly..
5*2=10
10*2=20

but i dont know how this is being executed.
 
Rob Spoor
Sheriff
Pie
Posts: 20659
64
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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))))
 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
     
    Anuradha Karunamuni
    Ranch Hand
    Posts: 64
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    Rob Spoor
    Sheriff
    Pie
    Posts: 20659
    64
    Chrome Eclipse IDE Java Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Sheriff
    Posts: 11343
    Java Mac Safari
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Originally posted by Rob Prime:
    Calling bunnyEars with a negative value will end...

    Good point.
     
    Anuradha Karunamuni
    Ranch Hand
    Posts: 64
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Sorry guys...My mistake ...(bunnies<=0) should be replaced with (bunnies>=0)...
    Or else follow Rob's method, it seems more practical.

    Sorry again...
     
    • Post Reply
    • Bookmark Topic Watch Topic
    • New Topic