Java Recursion method

Question

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;
   }
}

My question is how does 1 is incremented on each iteration? Please clarify. — Coda17
– Coda17, Commented May 22, 2014 at 16:25
@devnull that should be ln(n)/ln(2) + 1, or log-base-2(n) + 1 — ajb
– ajb, Commented May 22, 2014 at 17:18
Possible duplicate of Understanding how recursive functions work — user719662
– user719662, Commented May 27, 2016 at 18:46

AntonH · Accepted Answer · 2014-05-22 16:36:16Z

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

edited May 22, 2014 at 16:36

answered May 22, 2014 at 16:28

AntonH

6,4474 gold badges32 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

AntonH · Accepted Answer · 2014-05-22 16:29:57Z

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.

edited May 22, 2014 at 16:29

AntonH

6,4474 gold badges32 silver badges40 bronze badges

answered May 22, 2014 at 16:28

ajb

31.8k4 gold badges63 silver badges86 bronze badges

Comments

Maxim Bernard · Accepted Answer · 2014-05-22 16:28:56Z

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.

answered May 22, 2014 at 16:28

Maxim Bernard

3051 silver badge7 bronze badges

Collectives™ on Stack Overflow

Java Recursion method

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related