Results 1 to 4 of 4
  1. #1
    LifeWithJava is offline Member
    Join Date
    Dec 2008
    Posts
    7
    Rep Power
    0

    Default Understanding this recursive function

    Hi guys, I have been having a problem understanding this particular piece of code, which is a recursive function that prints a string backward..


    Java Code:
    public static void writeBackward(String s) {
          if (s.length() > 0) {
             // write the rest of the string backward
             writeBackward(s.substring(1));  
             // [COLOR="DarkRed"]need help understanding what is 
             happening here, how does this technique work in writing 
             the string backward[/COLOR]
             // print the first character
             System.out.print(s.charAt(0));
             //[COLOR="DarkRed"]I dont understand why it is printing 
             the string from the first position (charAt(0), according to 
             the statement), when it should be printing from the last position 
              to the first. Unless I am somehow grossly missing out on something 
              here.[/COLOR]
          }
          System.out.println();
       }

    Appreciate your help in interpreting this, thanks :)

  2. #2
    Durnus is offline Member
    Join Date
    Dec 2008
    Posts
    6
    Rep Power
    0

    Default

    Sometimes it helps me when I come across recursion just to write all the functions inline with a sample parameter. (And then change it back, of course, so it works again.)

    PHP Code:
    public static void writeBackward(String s)//asd
    {
    	if (s.length() > 0)
    	{
    		writeBackward(s.substring(1))//sd
    		{
    			if (s.length() > 0)
    			{
    				writeBackward(s.substring(1))//d
    				{
    					if (s.length() > 0)
    					{
    						writeBackward(s.substring(1))//
    						{
    							if (s.length() > 0)
    							{
    								writeBackward(s.substring(1));//Doesn't get called.
    								System.out.print(s.charAt(0));
    							}
    						}
    						System.out.print(s.charAt(0));//d
    					}
    				}
    			System.out.print(s.charAt(0));//s
    			}
    		}
    		System.out.print(s.charAt(0));//a
    	}
    }
    Hope that helps.

  3. #3
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    9

    Default

    Trying to figure out a recursive method can be a real mind–twister.
    One way to explore this is to try to follow/print enough of the execution of each trip thru the method to get an idea of what's going on.
    Java Code:
    public class Test {
        public static void main(String[] args) {
            writeBackward("hello world", 0);
        }
    
        public static void writeBackward(String s, int count) {
            if (s.length() > 0) {
                // write the rest of the string backward
                System.out.println("recurse with \"" + s.substring(1) +
                                   "\"" + pad(count) + "  will print \"" +
                                    s.charAt(0) + "\" later");
                writeBackward(s.substring(1), count+1);
    
                // Since the line above called this method this next line
                // will have to wait until the chain/cascade of recursive
                // calls ends before it can execute. The order of execution
                // of these next lines will be in reverse order (inside-out)
                // relative to the initial chain of (recursive) calls.
                // print the first character
                System.out.printf("printing charAt(%2d)  ", count);
                System.out.print(s.charAt(0));
            }
            System.out.println();
        }
    
        private static String pad(int n) {
            String s = "";
            for(int i = 0; i < n; i++) {
                s += " ";
            }
            return s;
        }
    }

  4. #4
    LifeWithJava is offline Member
    Join Date
    Dec 2008
    Posts
    7
    Rep Power
    0

    Default

    Thanks guys for illustrating the process of how the recursive function works in this instance.

    What I understood was how the string length was being reduced with each call of the method, till the length was 0.

    What I did not understand was how the println(s.charAt(0)) statement caused the string to be printed backwards.

    My guess is that I was not getting the 'unwinding' part of the recursive function, where after the method has been called till the length of the string is 0, the unwinding portion of the recursion causes the string to be printed backwards, as shown by both pieces of code by hardwired and Durnus (thanks!)

    However, intuitively, I havent understood how the unwinding part works though...any advise? ?

Similar Threads

  1. [SOLVED] Trouble understanding or expressions
    By hungdukie in forum New To Java
    Replies: 1
    Last Post: 11-23-2008, 02:24 AM
  2. [SOLVED] Understanding if else statements
    By hungdukie in forum New To Java
    Replies: 6
    Last Post: 11-18-2008, 08:56 AM
  3. [SOLVED] Help with understanding nullpointexcepion
    By soxfan714 in forum New To Java
    Replies: 4
    Last Post: 11-11-2008, 05:51 AM
  4. Understanding Vectors
    By cbrown08 in forum New To Java
    Replies: 7
    Last Post: 11-05-2007, 07:56 PM
  5. Help with recursive function in java
    By cachi in forum Advanced Java
    Replies: 2
    Last Post: 07-31-2007, 07:51 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •