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


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: confused on this recursive method example

  1. #1
    Junior Member
    Join Date
    Mar 2014
    Posts
    11
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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?


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,286
    Thanks
    56
    Thanked 2,372 Times in 2,343 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,707
    Thanks
    25
    Thanked 338 Times in 313 Posts

    Default 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
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

Similar Threads

  1. Replies: 4
    Last Post: December 9th, 2013, 10:40 AM
  2. How to create this recursive method.
    By exodus2041 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: April 9th, 2013, 11:26 AM
  3. Help in understanding this recursive method
    By jameschristopher06 in forum Algorithms & Recursion
    Replies: 2
    Last Post: November 20th, 2012, 01:23 PM
  4. help with recursive method
    By mflb94 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 27th, 2012, 07:30 PM
  5. Problem with recursive method. Can you help?
    By TFLeGacY in forum Algorithms & Recursion
    Replies: 6
    Last Post: December 7th, 2011, 05:44 PM