Recursive sum function for a linked list in java

Question

I want to sum up all the values of a linked list recursively but it doesn't work. It says:

Cannot invoke "Element.sum()" because the return value of "Element.getNext()" is null

public class Element{
    private int value;
    private Element next;
}

public class MyList{
    private Element elements;
    public int sum(){
        if (elements == null) return 0;
            return elements.getValue() + elements.getNext().sum();
        }
    }
}

Answer 1

Here's a solution:

public class MyList{

    private Element elements;
    
    class Element{
        private int value;
        private Element next;
        Element(int value) {
            this.value = value;
        }
        public Element getNext() {
            return next;
        }
        public int getValue() {
            return value;
        }
        public void setNext(Element next) {
            this.next = next;
        }
        public int sum() {
            if (next == null) {
                return value;
            } else {            
                return value + next.sum();
            }
        }
    }

    public MyList(int data[]) {
        Element prev = null;
        for (int value : data) {
            Element e = new Element(value);
            if (prev == null) {
                elements = e;
            } else {
                prev.setNext(e);
            }
            prev = e;
        }
    }
    
    public int sum() {
        return elements == null ? 0 : elements.sum();
    }
    
    public static void main(String args[]) {
        MyList list = new MyList(new int[]{ 1, 2, 3});
        System.out.printf("sum = %d\n", list.sum());
    }
}

Answer 2

As it seems you are trying to learn about recursivity, and it seems you are really trying, I won't give you a complete solution here.

First I think you didn't provide the complete code, because as is it does not compile. You are calling elements.getNext().sum() meaning you have a sum() method on your class Element.

And this is actually one possible correct way, to have a sum method in you Element class, because you want recursivity to happen on every Element.

So as you started this way, you should continue to try this way: add a sum method on your Element class. And this is where you can do recursivity. Recursivity meaning to call again the same method either on another instance or with another parameter...

The other answer works, but will you learn about recursivity just by copying it ? I would suggest trying to do similar thing, but in the Element class, so you manage to do it by yourself

Answer 3

sum isn't even a method of Element, so the implementation shouldn't compile.

I'd pass the root element to an internal sum method which can be recursive, and keep the no-arg sum method public:

public class MyList {
    private Element elements;

    public int sum() {
        return sum(elements);
    }

    private int sum(Element e) {
        if (e == null) {
            return 0;
        }
        return e.getValue() + sum(e.getNext());
    }
}

Answer 4

public class Foo {

    public static void main(String[] args) {
        MyList myList = new MyList();

        for (int i = 1; i <= 10; i++)
            myList.add(i);

        System.out.println(myList.sum());   // 55
    }
}

final class MyList {

    private Element head;

    public void add(int value) {
        if (head == null)
            head = new Element(value);
        else {
            Element element = head;

            while (element.next != null)
                element = element.next;

            element.next = new Element(value);
        }
    }

    public int sum() {
        return head == null ? 0 : head.sum();
    }

    private static final class Element {

        private final int value;
        private Element next;

        public Element(int value) {
            this.value = value;
        }

        public int sum() {
            return value + (next == null ? 0 : next.sum());
        }
    }
}

Answer 5

I am a bit confused about the returning value when the list reaches zero size or empty. I assume the returning value at that instance shall be zero, which replaces the cumulative result of the summation, but still the returned value is the same!?

any elaboration is highly appreciated.

please note the code below, formed in Kotlin language.

fun main()
{
    val aList = listOf<Int>(1, 2, 3, 4)
    val sumResult = sumListContents(aList)
    println(sumResult)
}

fun sumListContents(intNums: List<Int>): Int
{
    return if (intNums.isNullOrEmpty())
    {
        println("--------------$intNums-------------")
        0
    }
    else
    {
        println("${intNums[0]} $intNums sub list: ${intNums.subList(1, intNums.size)}")
        return intNums[0] + sumListContents(intNums.subList(1, intNums.size))
    }
}