Java summing recursive method

Question

I am given an array of integers, and trying to define a recursive method sum(int[] A,int s, int e) to calculate the sum of array A, where s and e are starting index and ending index. I want to test it with a given array int[] A= {3,5,8,9,10}.

I am confused on how to do this but here is what I have so far (I am even a little confused on the code here because my buddy helped me write it, a little explanation would help a lot!):

public static int sum(int[]A,int s,int e) {
   if (s==e)
      return A[e];
else
   return A[5] + sum(A,s+1,e);

Why to use recursive calls in such algorithms?? It's bad approach. — Stanislav Mamontov
– Stanislav Mamontov, Commented Oct 21, 2013 at 14:35
There's a mistake in the last line; it should be return A[s] ... not return A[5] .... Other than that, what exactly are you confused about? — Anthony Grist
– Anthony Grist, Commented Oct 21, 2013 at 14:37
@StanislavMamontov, the answer is almost certainly "to learn about recursion." — pamphlet
– pamphlet, Commented Oct 21, 2013 at 14:37
@pamphlet One of the biggest mistakes people make with recursion, is using it when it's completely unnecessary. The tutor, or whoever is teaching them, should use an example fit for recursion, so they can see why it's so useful it it's context. — christopher
– christopher, Commented Oct 21, 2013 at 14:39

Cruncher · Accepted Answer · 2013-10-21 15:11:37Z

As posted in @KlasLindbäck's answer, the 5 should be an s.

public static int sum(int[]A,int s,int e) {
   if (s==e)
      return A[e];
else
   return A[s] + sum(A,s+1,e);

To provide an explanation:

Firstly, to call this method:

int theSum = sum(myArray, 0, myArray.length-1);

I'll run through this for you {3,5,8,9,10} array.

sum(A, 0, 4):
return A[0] + sum(A, 1, 4)   //3 + sum(A, 1, 4)

sum(A, 1, 4):
return A[1] + sum(A, 2, 4)   //5 + sum(A, 2, 4)

sum(A, 2, 4):
return A[2] + sum(A, 3, 4)   //8 + sum(A, 3, 4)

sum(A, 3, 4):
return A[3] + sum(A, 4, 4)   //9 + sum(A, 4, 4)

sum(A, 4, 4):
return A[4]                  //10

Now, we know that sum(A, 4, 4) is 10, so therefore sum(A, 3, 4) is 9 + 10 = 19.
Now, we know that sum(A, 3, 4) is 19, so therefore sum(A, 2, 4) is 8 + 19 = 27.
Now, we know that sum(A, 2, 4) is 27, so therefore sum(A, 1, 4) is 5 + 27 = 32.
Now, we know that sum(A, 1, 4) is 32, so therefore sum(A, 0, 4) is 3 + 32 = 35.

Klas Lindbäck · Accepted Answer · 2013-10-21 14:36:25Z

1

You have missread one character. The 5 should be an s on the return line:

return A[s] + sum(A,s+1,e);

answered Oct 21, 2013 at 14:36

Klas Lindbäck

33.4k5 gold badges61 silver badges85 bronze badges

Comments

Abdulrahman Alsaadi · Accepted Answer · 2014-12-26 23:38:31Z

  package com.TTC.Tryfon.AbdulRahman;

public class Doing {
    public static void main(String[] args) {
        int [] z={3,5,8,9,10};
        System.out.println(sum(z,0));   
    }

    public static int sum(int [] a,int index){
        if(index<a.length){
            return a[index]+sum(a,index+1); 
        }
        return 0;   
    }

}

The above program will produce the following result:

In order to understand the program lets execute this part:

if(index<a.length){
    return a[index]+sum(a,index+1); 
}

index start as 0, and a.length=5:

if(0<5){
    return a[0]+sum(a,0+1);
    // this means return 3+sum(a,1);    
}

if(1<5){
    return a[1]+sum(a,1+1);
    // this means return 5+sum(a,2);    
}

if(2<5){
    return a[2]+sum(a,2+1);
    // this means return 8+sum(a,3);    
}
if(3<5){
    return a[3]+sum(a,3+1);
    // this means return 9+sum(a,4);    
}
if(4<5){
    return a[4]+sum(a,4+1);
    // this means return 10+sum(a,5);   
}
if(5<5){
    // 5 is not smaller than 5, so it will return 0;
    }
return 0;

since there is no more function call, we must replace the returned number by the function call:

10+0
9+10
8+18
5+27
3+32 =35

This is my first explanation ever, I hope it is good.

user278064 · Accepted Answer · 2013-10-21 14:52:29Z

0

You can also include the stop condition within the recursive call:

public static int sum(int[]A,int s,int e) {
     return A[s] + (s == e) ? 0 : sum(A, s+1, e);
}

answered Oct 21, 2013 at 14:52

user278064

10.2k1 gold badge36 silver badges48 bronze badges

1 Comment

Anthony Grist Over a year ago

Sure, you can. But saying "You can also do this" and throwing in operators they've likely not seen before, without explaining what it is and how it works, seems slightly ridiculous when they've said they don't really understand what's going on in the more readable version as it is.

Collectives™ on Stack Overflow

Java summing recursive method

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related