CODEWITHSUNDEEP
javarecursion
Shaikh Sakib
Shaikh Sakib

Reputation: 109

Recursion gives unexpected/wrong output?

So I was doing a recursion challenge on codingbat and came across the "bunny ears" problem where we have a number of bunnies and each bunny has two big floppy ears. We want to compute the total number of ears across all the bunnies recursively (without loops or multiplication).

The solution apparently is quite simple: 

public int bunnyEars(int bunnies)
{
    if(bunnies == 0)
        return 0;
    return 2+bunnyEars(bunnies-1);
}

But I am not able to understand. If we pass 2 in the bunnyEars(2) method the recursive part bunnyEars(bunnies-1); should have 1 left in the bracket after subtraction and thus 2+(1); which should be equal to 3 and not 4.
But the output comes as 4. So how does recursion actually work in this code?

Upvotes: 1

Views: 741

Answers (2)

Mark Adelsberger
Mark Adelsberger

Reputation: 45659

if we pass 2 in the bunnyEars(2) method the recursive part bunnyEars(bunnies-1); should have 1 left in the bracket after subtraction and thus 2+(1); should be equal to 3 and not 4.

It seems you're misreading the expression. The line of code in question says 

return 2+bunnyEars(bunnies-1);

Now you call bunnyEars(2), so bunnies == 2; and then you reach this line of code. 

return 2+bunnyEars(bunnies-1);

resolves to

return 2+bunnyEars(2-1);

or

return 2+bunnyEars(1);

So a second instance of the bunnyEars() function starts running, with bunnies == 1. It reaches that same line of code, and this time

return 2+bunnyEars(bunnies-1);

is

return 2+bunnyEars(1-1);

or

return 2+bunnyEars(0);

So a third instance of bunnyEars() gets running, with bunnies == 0; but this matches your base case, so you just return 0 ; this time we don't recurse. So back up a level we find that

return 2+bunnyEars(0);

is

return 2+0; // because bunnyEars(0) returned 0

so that instance returns 2. And that means

return 2+bunnyEars(1);

becomes

return 2+2; // because bunnyEars(1) returned 2

And of course 2+2 is 4, the correct answer.

It seems as though you applied the -1 to the return value of the recursive bunnyEars() call, but the code says to apply it to the parameter you're sending in, not to the return value.

Upvotes: 0

Yunnosch
Yunnosch

Reputation: 26703

It is not 2+(1), it is 2+numberOfEarsOfBunnies(1) == 2+2.
I renamed the function a little to make it more obvious.

Or even more into detail:

numberOfEarsOfBunnies(2)==
2+numberOfEarsOfBunnies(1)==
2+(2+numberOfEarsOfBunnies(0))==
2+(2+0)==
2+2==
4

Upvotes: 2

Related Questions