Sum of List<Integer> recursively

Question

Hello fellow programmers.

I am having a very silly problem.. I'm supposed to sum all the integers in a List, recursively. I know that there is an easier way to do this, and I actually made that method too (see class below). But the meaning of this assignment is that I have to split the list up into 2 halves and then calculate the sum recursively on both halves, and last I just return half1 + half2.

The problem is that the advanced method does not return the sum of all values. Can anyone please help me?

The method sum is the simple method. Summer(Summarize in danish) is the more advanced method.

package opgave1;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class BinærSøgning {
    public static void main(String[] args) {
        Random random = new Random();
        int tal = 3;

        List<Integer> liste = new ArrayList<Integer>();
        for (int i = 0; i < 10; i++)
            liste.add(random.nextInt(10));
        Collections.sort(liste);

        System.out.println(liste);
        //      System.out.println(binærSøgning(liste, 0, tal));
        System.out.println(summer(liste, 0));
    }

    public static int binærSøgning(List<Integer> liste, int start, int find) {
        if (liste.size() > 0) {
            int midt = liste.size() / 2;
            if (liste.get(midt) == find)
                return start + midt;
            else if (liste.size() > 1) {
                if (find < liste.get(midt))
                    return binærSøgning(liste.subList(0, midt), start, find);
                else
                    return binærSøgning(liste.subList(midt + 1, liste.size()), start + midt + 1, find);
            }
        }
        return -1;
    }

    public static int sum (List<Integer> list, int i)
    {
        if (i == list.size())
            return 0;
        else
            return list.get(i) + sum(list, i+1);
    }


    public static int summer(List<Integer> list, int start){
        int right = 0;
        int left = 0;

        if(start == list.size()){
            return 0;
        } else {

            int mid = list.size() / 2;
            if(start < mid){
                left += list.get(start) + summer(list.subList(0, mid), start+1);
            } else if(mid < list.size()){
                right += list.get(mid) + summer(list.subList(mid+1, list.size()), mid+1);
            }
        }
        return right + left;
    }


}

Answer 1

Are you sure that you have to split the list? Usually, when you get this task for homework, the meaning is something like:

public static int sum(List<Integer> l,int start) {
if (start==l.size()) return 0;
return l.get(start)+sum(l,start+1);
}

Answer 2

You are missing out elements of list when you are sending start+1 in the recursion.

     left += list.get(start) + summer(list.subList(0, mid), start+1);

You should rather send

      left += list.get(0) + summer(list.subList(1, mid), 0);

and

      right += list.get(mid) + summer(list.subList(mid+1, list.size()), 0);

I dont see the need to sending any start value. Every recursion should take the 0 in place of start.

Answer 3

I think it can be solved in a simpler way, by keeping track of both the first and last index of the range, like this:

public static int sum(List<Integer> list, int i, int j) {
    if (i == j)
        return list.get(i);
    int half = (i + j) / 2;
    return sum(list, i, half) + sum(list, half + 1, j);
}

It's called like this:

List<Integer> list = Arrays.asList(1, 2, 3);
System.out.println(sum(list, 0, list.size()-1));

It will work fine for non-empty lists. If the list is empty, you'll need to check it before calling sum.

Answer 4

Ii's much easier with two base cases, there is no need for an extra 'start' parameter if you use sublists. (Because it's homework, I won't fill in the details.)

public static int summer(List<Integer> list) {
   //base 1
   if (list.size() == 0) {

   }
   //base 2
   else if (list.size() == 1) {

   }
   else
   {
      //no need for if statements now!
      int left = summer(list.sublist(/* */))
      int right = summer(list.sublist(/* */))
      return left + right;
   }
}

Answer 5

First of all, you don't need to cut the list in half if all you need to do is use recursion. The sum of the elements of a list is the sum of its first element + the sum of all the elements of the rest of the list.

Second, your method is too complex. The sum of the elements of the list is 0 if the list is empty, the unique element is it contains 1 element, and the sum of the results of the method applied to the two sublists if it contains more than 1. You don't need any start argument.

This should get you started.

EDIT: since Oscar Lopez gave you the answer, but I find it too complex, here's mine:

public static int sum(List<Integer> list) {
    if (list.isEmpty()) {
        return 0;
    }
    else if (list.size() == 1) {
        return list.get(0);
    }
    else {
        int half = list.size() / 2;
        return sum(list.subList(0, half)) + sum(list.subList(half, list.size()));
    }
}

Answer 6

I am wondering a reason of getting a "half" of the List.
The solution for the question is the one and only:

public int sum_list(List<Integer> list) {
    if (list == null || list.isEmpty()) {
        return 0;
    }
    return list.remove(0) + sum_list(list);
}

Answer 7

import java.util.*;

public class SumListByRecursion {

    public static int sumByRec(List<Integer> list) {


        int size = list.size();
        if(size > 0) {
            return list.get(0) + sumByRec(list.subList(1, size));           
        }
        return 0;
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<Integer> list = new ArrayList<Integer>();

        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

        System.out.println("List:"+" "+list);

        int sum = sumByRec(list);
        System.out.println("Sum of the list:"+" "+sum);
    }

}