hi guys I just learned about recursive and need some help here:
Write recursive method sum that return the sum of all int elements in a linked structure. Use recursions. Do not use loop
publicint sumLinked(IntNode first){
int sum = 0;
if (first.next ==null)
return sum;
else{
sum += first.data;
return sumLinked(first.next);
}
}
what's wrong with this? where did I go wrong?.
Try tracing through the program yourself with a piece of paper.
I get you started. Lets consider the list has only one item and a reference to this item is passed to the parameter first. Your program intialises the sum variable to zero. Then it hits the if statement. If you have got the IntNode class correct then next will be null and the it statement is true, so it enters. What does it return? Zero! I guess this will work as long as the IntNode object contains the value 0.
I was expecting so that this test would pass:
@Test
public void testSumLinked(){
IntNode first = new IntNode(1, null);
first = new IntNode(3, first);
first = new IntNode(5, first);
first = new IntNode(7, first);
assertEquals(16, sumLinked(first));
}
and my IntNode class is:
public class IntNode {
private int data;
private IntNode next;
public IntNode(int element, IntNode nextNode) {
data = element;
next = nextNode;
}
}
So what do you want us to do? Just give you the code. I suggest you go and get your teacher to explain it because the best way to understand is to trace through the program on a piece of paper (which you seem unwilling to do) and your teacher can fill up an entire whiteboard explaining it to you. Something that will be difficult to do on a static forum.
> Yes I did, but I don't get what you mean
In that case drop the course. However, if you are determined to understand I will try and speak more slowly. Lets say you list contains one item which hold the value 5.
IntNode first
--
data = 5
next = null
--
You declare a variable sum and give it an initial value of ZERO.
Execute if statement: is first.next equal to null? Yes so enter if
return sum. Sum has what value? ZERO!
So the value that is always returned for the last element in the list will be ZERO and not FIVE. Is that clear?
That will have absolutely ZERO affect!
Now repeat after me:
MY PROGRAM WILL ALWAYS RETURN ZERO!
MY PROGRAM WILL ALWAYS RETURN ZERO!
MY PROGRAM WILL ALWAYS RETURN ZERO!
MY PROGRAM WILL ALWAYS RETURN ZERO!
MY PROGRAM WILL ALWAYS RETURN ZERO!
MY PROGRAM WILL ALWAYS RETURN ZERO!
MY PROGRAM WILL ALWAYS RETURN ZERO!
MY PROGRAM WILL ALWAYS RETURN ZERO!
MY PROGRAM WILL ALWAYS RETURN ZERO!
MY PROGRAM WILL ALWAYS RETURN ZERO!
why does it always return 0? The link is not empty, it has values 7,5,3,1. Why would then the first if statement be executed.
I change it also to this:
public int sumLinked(IntNode first){
int sum = 0;
if (first == null)
return sum;
else{
sum += first.data;
first = first.next;
return sumLinked(first);
}
}
Thankyou for making me do your work for you. If you had gotten a piece of paper and traced through your code like I said you would see. BUt now you've made me do it for you. I better get some damn dukes out of this.
List contains 2 nodes: 5 and 7.
IntNode Five
--
data = 5
next = Seven
--
IntNode Seven
--
data = 7
next = null
--
public int sumLinked(Five) { // node Five past as parameter
int sum = 0; // 1
if (first.next == null) { // 2
return sum;
} else { // 3
sum += first.data; // 4
return sumLinked(first.next); // 5, 9
}
}
public int sumLinked(Seven) {
int sum = 0; // 6
if (first.next == null) { // 7
return sum; // 8
} else {
sum += first.data;
return sumLinked(first.next);
}
}
OK. The numbers in the comments are the order that lines of code and executed.
1. Declare a local variable sum with value 0
2. If statement is false
3. Execute else branch
4. Sum is assigned the value 5
5. Make recursive call passing Seven
6. Declare a local variable sum with value 0. This is a different varaible to the one declared in point 1.
7. If statement is true so enter.
8. return sum (which has the value 0) to 5.
9. The return statement can be executed which will return the value it got from 8. Which is (all together now) ZERO!
You aren't adding the sum you compute at the current recursion level to the sum you compute at the next recursion level, so you are throwing away the result of sum += first.data.
The source of confusion is that every time you call a method, including recursion, you get a new set of local variables, i.e. in this case 'sum', which exist for the life of the method. So if you are recursing 3 deep there are 3 distinct 'sum' variables.
flounder explained it incorrectly as executing a separate but identical block of code.
You did, but it's not just a matter of pronunciation, or of different ways of looking at it. Describing recursion as executing a separate block of code is just factually incorrect as well as confusing to the OP. All you get is a new stack frame for the local variables, and that's all he needs to know about..
public int sumLinked(IntNode first){
int sum = 0;
if (first.next == null)
return sum; //1
else{
sum += first.data;
return sumLinked(first.next); //2
}
}
This was your original code. The errors here are in what you return. In line //1 you should return the value of the current node, otherwise you will never include the value of the last node. In line //2 you should add sum to your return value. If you don't you just return the value of the last element in the list (which in your case is 0 since you don't return the value, but the value of sum you just initialised to 0. (as flounder tried to explain)
Soz to interrupt but if your code is returning sum which has been initialized to 0, everytime you recursively call the method it will be initialised to zero, so the return statement will return the value 0 becuase of the
int sum = 0;
Correct me if i am wrong.
> so I should change it into if (first.data != null) ?
> how do I solve for the sum?
private static int sumLinked(IntNode node)
{
if(node == null)
return 0;
else
return node.data + sumLinked(node.next);
}
This code will check if the current node passed in is null, if it is, return 0, otherwise, return the sum of the current node.data and the result of the recursive call to sumLinked. This way you are only checking if the current node is null, and don't care if the next node is null. it will result in one more call than absolutely necessary, but that is a minor point with this simple of a program, and this way looks much clearer as far as I am concerned.
>yeah I understand about this, but still I do need a variable to store the >value of the sum right? then how would I do this? declare sum >outside?
yeah, you can declare int sum=0; at the top as global/memeber variable and then your done! you have to delcare it as static though. i think!
Oh dear, oh dear: the sum of all elements in a list is either (by definition?)
equal to zero if the list is empty or it is the value of the first node plus
the sum of the rest of the list.
No need for whatever (non)static or (non)local variables.
kind regards,
Jos
> ok, ill start on it right away.
>
> please provide your full name, and the name of the
> course, name of the professor so i may put it in
> header comments.
>
> i think i should be able to do it in under an hour,
> please respond fast
Hmm, haven't I seen this post somewhere before? That was a hilarious thread!
