RecursiveFunctionNeedsIfElse

Correction

Here is what's right.

Sometimes a simple if statement, without an else, can be enough.

This kind of single-branch if statement in a recursive function is common when the computation involves side effects (is not a pure function) and the base case means “no action”.

Another situation where no if-else statement is needed is if the recursive call is polymorphic, and one of the possible call targets corresponds to the base case:

class List:
	...

class Nil(List):
    def contains(self, value: int) -> bool:
        return False

class Cons(List):
    def __init__(self, value: int, tail: List):
        self.value = value
        self.tail = tail

    def contains(self, value: int) -> bool:
        return self.value == value or self.tail.contains(value)

The recursive call site represents a dynamic dispatch, either to Nil.contains() (base case) or to Cons.contains() (recursive case).

Origin

Where could this misconception come from?

This misconception might just be students inappropriately refining the “mantra” that you need a base case and a recursive case i.e, “you need an if branch and an else branch”.

However, it could also be that this misconception is more about if statements than about recursion. For example, if students previously learned functional programming with a textbook like HtDP, then they are used to pure functions built from expressions with if or cond. And such conditional expressions have to explicitly cover all cases (e.g., there must always be an else case in the if).

Value

How can you build on this misconception?

Students who hold this misconception seem to have internalized that one does need a base case and a recursive case to properly implement a finite recursive computation.

This is valuable!