1

The below method return 5 if you give n = 20.
My question is how is 1 incremented on each iteration? 

mystery(10) + 1 
= mystery(5) + 2 
= mystery(2) + 3 
= mystery(1) + 4 
= mystery(0) + 5 = 5.

I am having some hard time with recursion.

public static int mystery(int n){
   if(n <= 0){
        return 0;
   }else{
       return mystery(n / 2 ) + 1;
   }
}
amphetamachine
  • 27,620
  • 12
  • 60
  • 72
Bob
  • 564
  • 2
  • 10
  • 25
  • 1
    My question is how does 1 is incremented on each iteration? Please clarify. – Coda17 May 22 '14 at 16:25
  • Step through this in a debugger - all will be answered – KevinDTimm May 22 '14 at 16:27
  • Simply put you could think that it returns `ln(n) + 1`. – devnull May 22 '14 at 17:12
  • @devnull that should be `ln(n)/ln(2) + 1`, or `log-base-2(n) + 1` – ajb May 22 '14 at 17:18
  • @ajb I thought that base 2 was obvious. – devnull May 22 '14 at 17:20
  • @devnull `ln` means "log to the base _e_", period. It stands for "natural log". `log` can sometimes be ambiguous and could mean base-_e_, base-10, or base-something-else-obvious. But not `ln`. – ajb May 22 '14 at 17:24
  • 2
    Possible duplicate of [Understanding how recursive functions work](http://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work) –  May 27 '16 at 18:46

3 Answers3

8
mystery(20) = mystery(10) + 1
mystery(20) = (mystery(5) + 1) + 1
mystery(20) = ((mystery(2) + 1) + 1) + 1
mystery(20) = (((mystery(1) + 1) + 1) + 1) + 1
mystery(20) = ((((mystery(0) + 1) + 1) + 1) + 1) + 1

and we know that mystery(0) = 0.

mystery(20) = ((((0 + 1) + 1) + 1) + 1) + 1
mystery(20) = (((1 + 1) + 1) + 1) + 1
mystery(20) = ((2 + 1) + 1) + 1
mystery(20) = (3 + 1) + 1
mystery(20) = 4 + 1
mystery(20) = 5

Or, simply put, we get 1+1+1+1+1=5

Pretty good video on recursion here: https://www.youtube.com/watch?v=Mv9NEXX1VHc

AntonH
  • 6,359
  • 2
  • 30
  • 40
3

Looking at the code should make it obvious that:

mystery(20) = mystery(10) + 1
mystery(10) = mystery(5) + 1
mystery(5) = mystery(2) + 1
mystery(2) = mystery(1) + 1
mystery(1) = mystery(0) + 1
mystery(0) = 0

Now go back and plug in all the values, e.g.

mystery(1) = mystery(0) + 1 = 0 + 1 = 1
mystery(2) = mystery(1) + 1 = 1 + 1 = 2
mystery(5) = mystery(2) + 1 = 2 + 1 = 3, etc.
AntonH
  • 6,359
  • 2
  • 30
  • 40
ajb
  • 31,309
  • 3
  • 58
  • 84
1

Every time mystery() is called, it returns the value returned by calling itself, plus 1. So, for every call, the returned number gets incremented by 1.

Maxim Bernard
  • 307
  • 1
  • 7