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

Thread: Simple recursion logic

  1. #1
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

    Default Simple recursion logic

    can any one help me figure out how this recursion done?

    public class RecursiveMethodSum {
     
        public static int sum(int n) {
     
            if (n == 1) {
     
                return 1;
            }
            else {
     
                return n + sum(n - 1);
            }
        }
     
        public static void main(String[] args) {
     
            int x = sum(4);
     
            System.out.println(x);
        }
    }

    output
    10



    one question is... during the process of the recursion... (4 + (4 -1)) its == 7? ryt?
    but where does the number seven goes? i can only see the the process is just adding
    the value that has been passed to the parameter... where are the sum(s)?


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Simple recursion logic

    Remember, you have to traverse down to the lowest level before back-tracing in a recursive algorithm.

    So, the first recursive call would be:
    sum(4) = 4 + sum(3-1)
    sum(3) = 3 + sum(3-1)
    sum(2) = 2 + sum(2-1)
    sum(1) = 1

    So, the end result is:

    sum(4) = 4 + 3 + 2 + 1

    This doesn't really illustrate the order operations are done, though. Instead, the computer would evaluate it this way:

    sum(4) = 4 + (3 + (2+ (1)))

    So, the number 7 never shows up.

  3. The Following User Says Thank You to helloworld922 For This Useful Post:

    chronoz13 (December 24th, 2009)

  4. #3
    Junior Member
    Join Date
    Dec 2009
    Posts
    2
    Thanks
    0
    Thanked 1 Time in 1 Post

    Default Re: Simple recursion logic

    A recursive call is just like any other method call:

    public int ReturnOne() {
         return 1;
    }
     
    public static void main(String[] args) {
     
        int two = ReturnOne() + ReturnOne();
     
        System.out.println(two);
    }

    In the above the result of the two is initially null then it's 1 after the first method call, then it's two after the second method call. While the method calls are made the intermediate value of two is stored on a call stack by the java virtual machine.

    The same applies for recursion. In your case this is what happens:
    the method sum(int n) is called with value 4
    return value stored on stack is 4
       method sum(int n) is called with value 3
       return value stored on stack is 3
          method sum(int n) is called with value 2
          return value stored on stack is 2   
             method sum(int n) is called with value 1
             return value is 1
          return value is (stack value) 2 + (returned value) 1 = 3
       return value is (stack value) 3 + (returned value) 3 = 6
    return value is (stack value) 4 + (returned value) 6 = 10
    Last edited by myCoffee; December 24th, 2009 at 03:56 PM.

  5. The Following User Says Thank You to myCoffee For This Useful Post:

    chronoz13 (December 24th, 2009)

  6. #4
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

    Default Re: Simple recursion logic

    ahh so thats how recursion process works...

    im just confuse where does the value go every time it evaluates....

    so thats it... tnx guys...

Similar Threads

  1. Replies: 5
    Last Post: April 22nd, 2013, 07:27 AM
  2. not so simple, simple swing question box
    By wolfgar in forum AWT / Java Swing
    Replies: 2
    Last Post: November 20th, 2009, 03:47 AM
  3. Problems with recursion
    By KingLane in forum Algorithms & Recursion
    Replies: 4
    Last Post: September 20th, 2009, 11:02 PM