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 2 of 2

Thread: Can't understand simple Recursion:

  1. #1
    Member
    Join Date
    Oct 2013
    Posts
    31
    Thanks
    12
    Thanked 0 Times in 0 Posts

    Default Can't understand simple Recursion:

     
    class RecursionTest
    {
       public static void main(String[] args)
       {
     
           System.out.println(reverse("ABCDEF"));
       }
       //----------------------------------
       public static String reverse(String z)
       {
          if (z.length() <= 1)
             return z;
          return
             reverse(z.substring(1, z.length())) + z.substring(0, 1);
       }
    }


    Output:
    FEDCBA


    I understand that s.substring(1, s.length()) is the tail of the string, BCDEF and s.substring(0,1) is just the first letter , A. But how does this method actually reverse it? Where is the increment/decrement located?


    The first time around passes the method BCDEF and concatenates A on the end.... then what?


    Edit: maybe it works something like this? :

    first time passing it- BCDEF is tail, keep A to the side because its last ---> BCDEF A


    now you get CDEF and take B from it, put it before A on the side --------> CDEF BA

    now its DEF.... put c next to b ------------------------------------------> DEF CBA

    EF, put D next to C------------------------------------------------> EF DCBA

    F--------------------------------------------------------------------> F EDCBA


    = FEDCBA


  2. #2
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 262 Times in 231 Posts

    Default Re: Can't understand simple Recursion:

    First call: ABCDEF > 1, so return a recursive call with the first character appended to the end. Which at this point is some undetermined string + A.
    Second call: BCDEF > 1, so return a recursive call with the first character appended to the end. Which at this point is some undetermined string + B.
    Third call: CDEF > 1, so return a recursive call with the first character appended to the end. Which at this point is some undetermined string + C.
    Fourth call: DEF > 1, so return a recursive call with the first character appended to the end. Which at this point is some undetermined string + D.
    Fifth call: EF > 1, so return a recursive call with the first character appended to the end. Which at this point is some undetermined string + E.
    Sixth call: F = 1, so return F.
    This is the turning point where the unknown strings are now known and the recursion starts to unwind.
    The string F is returned to the fifth call, which appends E, resulting in FE.
    FE is returned to the fourth call, which appends D, resulting in FED.
    FED is returned to the third call, which appends C, resulting in FEDC.
    FEDC is returned to the second call, which appends B, resulting in FDECB.
    FDECB is returned to the first call, which appends A, and finally exits the recursive method returning FEDCBA to where the method was first called.
    It is important to note that a recursive method stacks up all of the calls until the return is hit where the method does not call itself again. In this example, when the string was one character long the string F was the first real return value. All other calls were in memory waiting on that F to work it's way back to the start. The first call can not return until the second call does. The second call can not return until the third call does. So on and so on until there is no memory left or the method finally returns a value rather than calling itself again.

Similar Threads

  1. Please Help me to understand
    By Theillusion in forum What's Wrong With My Code?
    Replies: 2
    Last Post: January 17th, 2013, 02:09 AM
  2. Please help to understand whats the wrong with my guess. - Simple program
    By rayan2004 in forum Object Oriented Programming
    Replies: 1
    Last Post: December 14th, 2012, 12:03 AM
  3. Please help to Understand x=++x+ + +x+x++
    By rayan2004 in forum What's Wrong With My Code?
    Replies: 8
    Last Post: December 2nd, 2012, 06:47 PM
  4. Help me to understand this
    By Madhushan in forum Java Theory & Questions
    Replies: 2
    Last Post: September 10th, 2011, 08:47 AM
  5. Simple recursion logic
    By chronoz13 in forum Algorithms & Recursion
    Replies: 3
    Last Post: December 24th, 2009, 09:53 PM