Java- difference between return vs no return in iterated list recursion

Question

I am trying to count the number of items in a linked list that fit a condition (if x > num) using recursion and iterator. When I use return to self-call the function (as shown below) it returns a count of the items it goes through but doesn't go through the list but when I don't use return and would just call the function directly if(x > num) total = 1 + nodes.Greater(); else nodes.Greater(); it goes through the entire list but returns a count of 0 always.

public static Integer nodesGreater(Node x, Integer num) { 
 Integer total = 0;  
 for(Iterator<Integer> it = list.iterator(); it.hasNext();) {  
   Integer x = it.next();  
   if(x > num) return 1 + nodesGreater(it.next(), num);      
   else return nodesGreater(it.next(), num);     
 } 
 return total; 
}

For example, if the linked list is

1-3-8-10-12-15-20

and the condition is it should be greater than 8, it would return 2 (10, 12) instead of 4 (10, 12, 15, 20)

Your loop never loops: you always return on the first iteration. — Andy Turner
– Andy Turner, Commented May 12, 2021 at 10:51
(Also, this code doesn't compile, you have two it variables) — Andy Turner
– Andy Turner, Commented May 12, 2021 at 10:51
I'd rather us either an iterative approach or a recursive one, but mixing the two doesn't seem right here. — sp00m
– sp00m, Commented May 12, 2021 at 10:53
oh, sorry about that I was tidying up the code since the actual code was messy and I must've forgotten to remove the first it. — Leila K.
– Leila K., Commented May 12, 2021 at 11:03

rzwitserloot · Accepted Answer · 2021-05-12 10:54:35Z

You're doing it in both ways, incorrectly.

EITHER:

Use that listiterator and do not recurse, -OR-
Recurse, and don't use the list iterator

recursion is one strategy for looping through a list of items. an iterator is another. You're trying to do both. Hence, that does not work.

If you want to recurse, then the algorithm is the same as all recursion algorithms:

Check if you're being asked to operate on an edge case. If you do, return the obvious answer without recursion. Presumably, a node that has no 'next' node is that edge case, and you just return 1 (or possibly 0; depends on how you designed your linked list) straight up.
Otherwise, do the calculation for just your own element (presumably, that's a constant: your own node contributes a size of '1' to the answer, so '1'), invoke yourself on a known-simpler variant of your data structure (that'd be call nodesGreater on the node that is after yours, which is guaranteed to be closer to that edge case of the last node), and merge the results.
That's it. There's no looping.

So, something like:

if (x.next == null) return 1;
return 1 + nodesGreater(x);

Alternatively if you want to do the iteration, then just iterate through each element, figure out the answer for the node you're on, and merge it with a counter variable:

int sum = 0;
for (int elem : elems) sum++;
return sum;

NB: It's int, not Integer. Integer 'works', but that's the object ref wrapper for ints, you don't want it.

Collectives™ on Stack Overflow

Java- difference between return vs no return in iterated list recursion

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related