BaseCaseNotNeeded

DRAFT

Correction

Here is what's right.

Any terminating recursive computation needs some kind of base case.

The following directly-recursive method wihout base case represents a recursive computation that will not terminate:

// problem: missing base case
int sum(int n) {
  return n + sum(n - 1);
}

The following method does have a base case:

int sum(int n) {
  if (n <= 0) {
    return 0;
  } else {
    return n + sum(n - 1);
  }
}

This method has a base case as well, represented by a conditional operator:

int sum(int n) {
  return n <= 0 ? 0 : n + sum(n - 1);
}

The base case might be hidden within a polymorphic call site (which may dispatch to a base or recursive implementation of a method), and thus may not involve an explicit conditional statement or conditional operator:

public interface Node {
  public int len();
}
public class NodeBase implements Node {
  public int len() {
    return 0;
  }
}
public class NodeRec implements Node {
  public Node rest;        // can refer to a NodeRec or NodeBase
  public int len() {
    return 1 + rest.len(); // polymorphic call dispatches to base case
  }
}

No matter how the condition to dispatch between base case and recursive case is implemented, for a recursive computation to terminate there needs to be some base case.

Symptoms

How do you know your students might have this misconception?

It is not clear whether students truly believe that base cases are not needed. Chances are that they simply are overwhelmed by the complexity of recursion and never think of implementing the base case.

The following example shows a recursive method without base case. The student might have been confused by the presence of the if-statement, and they might have assumed that this statement somehow represents a base case.

int max() {
  int maxValue = 0;
  if (value>maxValue) {
    maxValue=value;
  }
  return tail.max();
}

Value

How can you build on this misconception?

Base Cases in Indirect Recursion

If a student has this misconception, it may be good to point out that in cases of indirect recursion, where several methods are involved in a recursive cycle, it is sufficient if one of them takes care of the base case. The other methods involved in the recursive cycle thus might not contain any code to deal with terminating the recursion.

Very Advanced: Recursion Without Base Case with Lazyness

For very advanced students, one could discuss how lazy languages (like Haskell) can have recursive functions without base cases and still have computations that terminate. For example, the function from in the following Haskell code is recursive, but it has no base case. In an eager language, any call of from would generate an infinitely long list. In Haskell, which is lazy, the call is not evaluated until it is needed. Thus, take 5 (from 0) will only lead to the first 5 elements of the infinitely long sequence being created, i.e., the first five invocations of from to be evaluated.

from n = n:(from (n+1))
take 5 (from 0)

If we translate the above code to Java, which eagerly evaluates method calls, we would need to introduce lambdas to make method calls behave lazily:

public class Cons {

  private int head;
  private Supplier<Cons> tail;

  private Cons(int head, Supplier<Cons> tail) {
    this.head = head;
    this.tail = tail;
  }

  public static Cons take(int n, Cons cons) {
    if (n == 0 || cons==null) {
      return null;
    } else {
      return new Cons(cons.head, () -> take(n - 1, cons.tail.apply()));
    }
  }

  public static Cons from(int n) {
    return new Cons(n, ()->from(n + 1));
  }

  public static Cons run() {
    return take(5, from(0));
  }

}

The fact that we have to implement lazyness manually, by introducing lambdas to defer computations (e.g., in take or in from), pushes the call sites that would appear as recursive in lazy Haskell into different functions (the lambdas). So, in the Java code, method take does not directly call method take. Instead, method take produces a lambda, that, when called later on, will call method take.

In this program, method from creates an infinitely long list, in a “recursive” way, without any base case, but it doesn’t run forever. This is because it doesn’t actually call from directly, but it produces the lambda that, when evaluated later, will call from again.