Simple recursion logic

**chronoz13** · December 24th, 2009, 02:31 AM

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

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

**helloworld922** · December 24th, 2009, 10:40 AM

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.

**myCoffee** · December 24th, 2009, 03:40 PM

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

**chronoz13** · December 24th, 2009, 10:53 PM

ahh so thats how recursion process works...

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

so thats it... tnx guys...

Thread: Simple recursion logic

LinkBack

Thread Tools

Display

Simple recursion logic

Related threads:

Re: Simple recursion logic

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

Re: Simple recursion logic

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

Re: Simple recursion logic

Similar Threads

Using recursion to find the number of occurences of a character in a string

not so simple, simple swing question box

Problems with recursion