Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

Thread: confused on this recursive method example

1. confused on this recursive method example

public int mystery (int k )
{

if ( k ==1 ) return 0;

else return ( 1 + mystery(k/2) );
}

the answer is 4, but I really don't understand how....anybody care to explain why this is?  Reply With Quote

3. Re: confused on this recursive method example

Try doing some debugging. Add some println statements to print out the values of variables as they are used. The printout will show you what the code is doing.  Reply With Quote

4. Re: confused on this recursive method example

Recursion has two important parts:
1. An "exit case" - where a condition is reached such that no more recursive calls are made. In your example, k==1 is the exit case.
2. The recursive call - where the recursive method calls itself. In your example, mystery(k/2)

An important thing to note here is integer division. When you divide two integers in Java, any fractional remainder is ignored. So: 4/2=2, 5/2=2, 6/2=3, 7/2=3, ect.
The numbers are not rounded or anything. The decimals are just simply tossed away.

When you call a method in Java, the method does not finish until the method is exited (with a return statement, if a return value is required).
When you call: return (1 + mystery(k/2);, the method doesn't "finish" until the value of (1 + mystery(k/2)) is finished calculating. Since the method calls itself, the "instance" of the method which called mystery(k/2) has to wait until mystery(k/2) is finished evaluating.

So, you can imagine the recursive calculations unraveling like this:
int value = mystery(9);
int value = (1 + mystery(9/2)) ** 9/2 = 4
int value = (1 + (1 + mystery(4/2)) ) ** 4/2 = 2
int value = (1 + (1 + (1 + mystery(2/2)) ) ) ** 2/2 = 1
int value = (1 + (1 + (1 + (1 + (0)) ) ) )
int value = (1 + (1 + (1 + (1)) ) )
int value = (1 + (1 + (2) ) )
int value = (1 + (3) )
int value = 4  Reply With Quote