BaseCaseSelfRecursive

DRAFT

Correction

Here is what's right.

In general, the base case of a recursive computation should not continue the recursive computation.

In the specific case of structural recursion (recursive computation over a recursive data structure), the base case of the computation (last invocation of the recursive method) corresponds to the base case of the data structure (last node of the recursive data structure).

class Node {
  Node next;

  public void traverse() {
    if (next==null) {
      // base case      -- don't call traverse()
    } else {
      // recursive case -- call traverse() on next
      next.traverse();
    }
  }
}

Symptoms

How do you know your students might have this misconception?

In the following example, while the first case is a traditional “recursive case”, where the next recursive call processes the next node of a recursive structure (next.length()), the second case is a “base case” in terms of the data structure (we look only at ourselves) but, erroneously, uses a recursive call (and thus triggers an infinite recursion):

public int length() {
  if (next!=null) {
    return next.length()+1
  } else {
    return length()+1 // why call this.length()? just return 1.
  }
}

The following example is very similar to the previous one:

public int max() {
  if (next!=null) {
    return value + next.max();
  } else {
    return max() + value; // why call this.max()? Just return this.value
  }
}

In the following example, the student did not use the proper syntax for method invocations, but tail.length and length probably was supposed to mean tail.length() and length(), given that the class had no instance variable with the name length:

public int length() {
  if (tail!=null) {
    tail.length + 1;
  }
  return length; // why "call" length? Just return 1
}

In the following example, the student used the proper method call syntax for the recursive case, but didn’t use that syntax for the base case. Maybe that student considered max to be some kind of variable holding the result (especially given that the method also does not contain any return statements)?

public int max() {
  if (tail!=null) {
    Math.max(tail.max(); value);
  }
  return max; // why "call" max? Just return value
}

In the following example, there is only one case: in terms of data structure, it processes the node itself (it’s a base case), but in terms of computation, it consists of a recursive call:

public int length() {
  return this.length() + 1; // why not just return 1? (plus add a proper recursive case)
}