Home > database >  Need help understanding basic recursion problem
Need help understanding basic recursion problem

Time:10-11

I have just started practicing with recursion I have this very simple practice program problem.

There are bunnies standing in a line, numbered 1,2,3... The odd bunnies (1,2,3..) have normal 2 ears.

The even bunnies (2,4,6...) have 3 ears, because they each have a raised foot. Recursively return the number of ears in the bunny line.

I have the solution. However, I am a bit confused on certain things. For one, it is my understanding that each even numbered rabbit has 3 feet. So bunnyEars2(2), should produce 6 instead of 5?

Also, I notice if I remove certain intricacies like '(bunnyEars2(bunnies)' instead of adding in the '-1' at the end. I get this duplicitous message "at bunnyEarsTwo.bunnyEars2(bunnyEarsTwo.java:13).

Any explanation and breakdown of this problem and recursion in general is very much appreciated. I am determined to learn, I just want to be pointed in the right direction!

 public static int bunnyEars2(int bunnies){
    if(bunnies==0) return 0;
    return (bunnies % 2 == 0) ? (3 bunnyEars2(bunnies-1)) : (2 bunnyEars2(bunnies-1));
}

CodePudding user response:

I hope you know factorial by recursive. because this is very similar.

int factorial(int n){    
  if (n == 0)    
    return 1;    
  else    
    return(n * factorial(n-1));    
 }   

Here we are returning `n * n-1 * n-1-1 * n-1-1-1 and so on until it n-1.... is 0.
Likewise,

public static int bunnyEars2(int bunnies){
    if(bunnies==0) 
        return 0;
    if (bunnies % 2 == 0)
        return  3 bunnyEars2(bunnies-1);
    else 
        return  2 bunnyEars2(bunnies-1);
}

Here, follows same logic, but the differece is ,
when its even, it return 3 bunnyEars2(bunnies-1)
when its odd, it return 2 bunnyEars2(bunnies-1)
for example: bunnyEars2(4) is 10
here our bunnies value will be 4,3,2,1,0
as 4 is even it returns 3 , 3 is odd it returns 2 , 2 returns 3 , 1 returns 2 and 0 returns 0
3 2 3 2 0 = 10.
bunnyEars2(2) will be 5, here bunnies value will be 2,1,0 which returns 3 2 0 = 5
Also removing -1 from bunnyEars2(bunnies-1) will result in infinite recursion(stack overflow error). It's like removing -1 from n * factorial(n), it won't end.

  • Related