Linked list recursion in Java

Question

I have to code a recursive method that iterates through a linked list and returns the number of integers that are positive. Here is the question:

The method countPos below must be a recursive method that takes a Node head as its argument, goes down the list headed by head, and counts the number of nodes which have a positive data field.

The code I have works however, I don't understand how it works.

public int countPos(Node head) {
    int count = 0; 
    if (head == null) { return count; }

    if (head.data > 0) {
        count++; 
        return count + countPos(head.next);
    } else {
        return count + countPos(head.next);
    }
}

The problem I'm having is I don't understand how count doesn't get set back to 0 every time the method is called. For some reason the statement int count = 0; is ignored the next time the method gets called. Is this because I'm returning count also? Any explanation would be greatly appreciated.

Thanks.

Answer 1

DON'T begin by tracing execution or debugging. The power of recursion is that it lets you reason about complicated programs with simple logic.

Your code works by chance. It reflects that whoever wrote it (you?) doesn't understand how recursion solves problems. It's more complex than necessary.

To exploit recursion, take the problem at hand and:

1. Define the function interface.
2. Split the problem into parts, at least one of which is a smaller version of the same problem.
3. Solve that (or those) smaller version(s) by calling the function interface itself.
4. Find the "base case" or cases that are solutions to very small instances of the same problem.

With all this done, the pseudocode for most recursive algorithms is:

function foo(args)

   if args describe a base case
     return the base case answer.

   solve the smaller problem or problems by calling foo with 
     args that describe the smaller problem!

   use the smaller problem solution(s) to get the answer for this set of args

   return that answer
end

Let's apply this to your case:

PROBLEM: Count the number of positive items in a list.

1. Define the function interface: int countPos(Node head).
2. Split the problem up into parts: Get the number of positives in the list remaining after the head, then add one if the head is positive and nothing if the head is zero or negative.
3. The smaller version of the problem is finding the number of positives in the list with head removed: countPos(head.next).
4. Find the base case: The empty list has zero positives.

Put this all together:

int countPos(Node head) {

  // Take care of the base case first.
  if (head == null) return 0;

  // Solve the smaller problem.
  int positiveCountWithoutHead = countPos(head.next);

  // Now the logic in step 2. Return either the positive count or 1+ the positive count:
  return head.data > 0 ? positiveCountWithoutHead + 1 : positiveCountWithoutHead;
}

You might learn a little bit by tracing execution of something like this one time. But trying to write recursive code by reasoning about what's going on with the stack is a dead end. To be successful, you must think at a higher level.

Let's try one that doesn't quite follow the standard template: Recursive binary search. We have an array a of integers and are trying to find the index of x if it exists in the array and return -1 if not.

PROBLEM: Search the array between positions i0 and i1-1.

(The above is an example of how you must sometimes "specialize" the problem by adding parameters so that smaller subproblems can be described in the recursive call or calls. Here we are adding the new parameters i0 and i1 so that we can specify a subarray of a. Knowing how and when to do this is a matter of practice. The parameters needed can vary with language features.)

1. Function interface: int search(int [] a, int x, int i0, int i1)
2. Split the problem in parts: We'll pick a "middle" element index: mid = (i0 + i1) / 2. Then the subproblem is either searching the first half of the array up to but excluding mid or the second half of the array starting after mid and continuing to the end.
3. The calls are search(a, x, i0, mid) and search(a, x, mid + 1, i1).
4. The base cases are that 1) if i0 >= i1, there are no elements to search, so return -1 and 2) if we have a[mid] == x, then we've found x and can return mid.

Putting this all together

int search(int [] a, int x, int i0, int i1) {

  // Take care of one base case.
  if (i0 >= i1) return -1;

  // Set up mid and take care of the other base case.
  int mid = (i0 + i1) / 2;
  if (a[mid] == x) return mid;

  // Solve one or the other subproblems.  They're both smaller!
  return x < a[mid] ? search(a, x, i0, mid) : search(a, x, mid + 1, i1);
}

And to start the search:

int search(int [] a, int x) { return search(a, x, 0, a.length); }

Answer 2

Each time you call countPos(), a new version of that function starts. This function starts from a clean slate meaning all of the local variables (count) are its own, and no other "copy" of countPos can see or modify its local variables.

The only state that is passed between these "copies" or of countPos is the variables that are passed in as parameters (Node head).

So here's a rough workflow assuming the list [1, -2, 3]

1. countPos starts, and says number of positive nodes is equal to 1, since "1" is positive. The total number of positive nodes is equal to 1 + whatever the next function returns.
2. The next function says the number of positive nodes is equal to 0 + whatever the next function returns.
3. The next function says the number of positive nodes is equal to 1 + whatever the next function returns
4. The next function sees that head == null and so returns 0.

Now each recursive function returns one after another to the original function that called it, with the total number of positive nodes "snowballing" as we return.

The total number returned in the end will be 2.