RecursiveCallSiteNoReturn

DRAFT

Correction

Here is what's right.

In any method (recursive or not) that has a non-void return type, every control-flow path needs to end in a return statement. A method with a non-void return type must return a value of that type, no matter what happens.

Chances are that students believe that recursive method calls are not really nested. They may believe that the base case is where the recursion, as a whole, returns, and that the recursive case thus does not need any return statement.

Examples

Example: Tail-recursive calls

The following code is broken and won’t compile:

int sum(int n, int s) {
  if (n==0) {
    // base case
    return s;
  } else {
    // recursive case
    sum(n-1, s+n); // tail-recursive call, no return
  }
}

The site calling sum(n-1, s+n) will have to do something with the return value of that call, and it has to return something. Here (a tail recursive call) there’s nothing to do but to return the value returned from the recursive call.

Another broken example with a tail-recursive call:

int indexOf(int i, int value, int[] values) {
  if (i==values.length) {
    // not found
    return -1;
  } else if (values[i]==value) {
    // found
    return i;
  } else {
    // recursive case
    indexOf(i+1, value, values);  // tail-recursive call, no return
  }
}

Example: Not tail-recursive calls

In methods that are not tail-recursive there is a lower risk for this misconception to occur, because there is a need to put some code after the recursive call, and chances are that this coding activity then triggers the creation of the necessary return statement.

Nevertheless, some students simply write the expression including the recursive call but omit a return statement:

int sum(int n) {
  if (n==0) {
    return 0;
  } else {
    n + sum(n-1); // unused expression, no return
  }
}

Example: Pass result via external accumulator variable

Instead of returning the result of the recursive call, as required by the method signature, the student uses an instance variable to accumulate the result.

    int k = 0
    public int length() {
        if (list==null) {
            return k;
        } else {
            k++ // mutate instance variable instead of returning value
            list.child.length() // recursive call, no return
        }
    }

Example: Pass result via local variable

Instead of returning the result, this student tried to use a local variable to accumulate the result of the recursive calls.

public int length() {
  int total = 0;
  if (this.tail==null) {
    return total;
  } else {
    total = 1 + this.tail.length(); // recursive call, assign to local variable, no return
  }
}