Lior Edison Mizrahi Lior Edison Mizrahi - 3 months ago 8
Java Question

recursion cannot get this right

We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.

triangle(0) → 0
triangle(1) → 1
triangle(2) → 3


This is my code:

public int triangle(int rows) {
int n = 0;

if (rows == 0) {
return n;
} else {
n = n + rows;
triangle(rows - 1);
}
}

Answer

When writing a simple recursive function, it helps to split it into the "base case" (when you stop) and the case when you recurse. Both cases need to return something, but the recursive case is going to call the function again at some point.

public int triangle(int row) {
  if (row == 0) {
    return 0;
  } else {
    return row + triangle(row - 1);
  }
}

If you look further into recursive definitions, you will find the idea of "tail recursion", which is usually best as it allows certain compiler optimisations that won't overflow the stack. My code example, while simple and correct, is not tail recursive.

Comments