# BaseCaseNotNeededDRAFT

Misconception:

A recursive computation does not necessarily need a base case. Methods can directly or indirectly call themselves without any of them including a decision to terminate the recursion.

Incorrect

Recursive computations do not necessarily need a base case

Correct

Recursive computations need a base case to terminate

## CorrectionHere 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.

## SymptomsHow 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();
}``````

## ValueHow 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 Supplier<Cons> tail;

private Cons(int head, Supplier<Cons> tail) {
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.

Java