Recursive Java Method

[dddx]

Hi Guys,

I'm back again with another question hoping you guys can help me out and point me to the right direction

I am supposed to write the body of a recursive Java method for the following, however after a few java courses and reading a lot about recursion, i sometimes still don't know how to come up with the right base and generic cases:

code:

public static int altSum(IntNode head, int i) which, when called as altSum(head, 1), computes the alternating sum of the elements in the IntMode-based linked-list with head-reference head, i.e. Sigma_{i=i}^{n}(sign(i) * val(i)) where n is the number of nodes in the list, val(i) is the value associated with the i-th element in the list, and sign(i) is 1 if i is odd and -1 if i is even. For example, given the list head [ ] --> [4][ ] --> [7][ ] --> [8][ ] --> [2][ ] --> [9][X] the alternating sum for thos list is 4+-7+8+-2+9=12.

I am not really clear where to start or what would be my base case and generic case? do i have to count the element and then use recursion as a count-down loop? All suggestions and comments are welcome. I am also not good with linked list so i will post a new topic as well with a few questions about Linked-List.

Thank you in advance
dddx

[DemonWasp]

Base case: what happens when the value of head is null?

General case: what happens when the value of head is not null? Can you express the value of a list in terms of its value and "the sum of the rest of the list"?

[dddx]

DemonWasp @ Mon Sep 26, 2011 2:41 pm wrote:

Base case: what happens when the value of head is null?

General case: what happens when the value of head is not null? Can you express the value of a list in terms of its value and "the sum of the rest of the list"?

Thanks DemonWasp,

I am a little confused with this one. I understand the words but I don't really get what is that the question wants. "...computes the alternating sum of the elements in the IntMode-based linked-list with head-reference head"

does this mean i have to get the sum of the elements passing through the method or sum of all elements of the linked list?

Thanks

[DemonWasp]

What they want is the following:

- They will give you the head node of a linked list (see the IntMode class).

- They want you to sum the nodes of that linked list in alternating order: the first node is positive, the second is negative; the third is positive, the fourth is negative (and so on).

[dddx]

I see. so for example, the first number is positive + the negative of the second one + the third + negative of the 4th and so on. Thanks DemonWasp, i think i got that part of the question now

So if the head is null then we are at the end and we stop.

But then what is the use of int i and the math formula in this method?

Thanks

[DemonWasp]

You use i to determine whether to add or subtract the value at that node. Try doing what it wants you to do with a small list. Do it on paper, with a pencil.

[dddx]

So basically i is the index and let's say if i=1, then we have 4-7+8-2+9
whereas if i=2, then we have 7-8+2-9 (start from second node)

Or

no matter what i is, we always add every element of the list starting with the first node, however, the value of i will only effect the sign of each element when they are being added.

Am i in the right direction or still far away from it?

Thanks

**Edit: I think i got how the negation and i works. Could you please check that if this is true: when i=2, then we get: -7+8-2+9 and when i=4 we get: -2+9
For base case, could i use n=1 so when it is over 1, i can use it as i and then deduct 1 from it?

One more thing, How can i count the number of nodes and element in the list?

**Edit: I think i got it. Here's what i figured and hopefully it's right:

code:

public static int altSum(IntNode head, int i) {      if (i%2==0)      {            int sign = -1;      }      else      {           int sign = 1;      }      if (head == null) //base case      {            return 0;      }      else //general case      {           return( (sign*list.get(i)) + (altSum(head.next, i++)) );      } }

[DemonWasp]

The code you posted is correct (or at least has the right idea, I haven't tested it).

[dddx]

DemonWasp @ Wed Sep 28, 2011 10:02 pm wrote:

The code you posted is correct (or at least has the right idea, I haven't tested it).

Thanks DemonWasp