Perform recursive analysis for for the problem of summation. Our goal is to impl

Question

Perform recursive analysis for for the problem of summation. Our goal is to implement a method called sumList that takes a reference to the first node (e.g., head) in a list of integers and returns the sum of its contents. By convention, the sum of an empty list will be zero. (You may want to look at the source code in the next question).

Using the fantastic four approach, determine the size n problem (i.e. the “whole problem”) for the method sumList.

Identify the stopping condition(s) and the return value, if any, for method sumList.

Determine the size m problem (i.e. the “subproblem”) for the method sumList. How does is the size-n problem constructed from the size m problem?

public class IntNode {

    private int value;

    private IntNode next;

    public IntNode(int i) { value = i; }

    public int getInt() { return value; }

    public void setInt(int v) { value = v; }

    public IntNode getNext() { return next; }

    public void setNext(IntNode n) { next = n; }

}

public class Sum {

    public static void main(String[] args) {

         IntNode a = new IntNode(10);

        //omitted: code appending more new elements to the list.

    int sum = sumList(a);

    System.out.println("The sum is " + sum);

    }

    //TODO: implement recursive sum implementation.

    public static int sumList(IntNode head) {

Explanation / Answer

public

class IntNode {
private int value;
private IntNode next;
public IntNode(int i) { value = i; }
public int getInt() { return value; }
public void setInt(int v) { value = v; }
public IntNode getNext() { return next; }
public void setNext(IntNode n) { next = n; }
}
public class Sum {
public static void main(String[] args) {
IntNode a = new IntNode(10);
//omitted: code appending more new elements to the list.

IntNode b = new IntNode(20);
a.setNext(b);
int sum = sumList(a);
System.out.println("The sum is " + sum);
}
//TODO: implement recursive sum implementation.
public static int sumList(IntNode head) {
   if(head == null){
       return 0;
   }
   return head.getInt()+sumList(head.getNext());
}

}

Output:

The sum is 30

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.