Using recursive calls without loops and multiplication to find values

user_13548832 0
Viewed 235

Consider this problem:

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.

My approach to this problem was this

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

The program works fine for values up to the number 3 but then the values that should come out are wrong (the calculation is wrong/recursive call). What am I missing?

Thank you in advance!

recursion java
3 Answers

You're adding 2 to your recursive invocation, try to add rows.

Example:

public int triangle(int rows) {
  if (rows < 2)
    return rows;
  else
    return triangle(rows - 1) + rows;
}
user_88818630

You have the right idea. You start from the "bottom" row and in each recursive call you move to the row above until you reach the top row, which contains only one block. Your only problem is that instead of adding 2, you need to add the number of rows.
(Explanations after the code.)

public int triangle(int rows) {
    if (rows < 1) {
        throw new IllegalArgumentException("'rows' must be positive.");
    }
    if (rows == 1) {
        return 1;
    }
    else {
        return rows + triangle(rows - 1);
    }
}

Let's take a simple example where you initially call the method triangle() with a value of 4. That means that the bottom row contains four blocks and the row above that contains three blocks. So the last return statement in the above code means:
Return the number of blocks in my row plus all the blocks that are above my row in the triangle.

So the method triangle() calls itself with the value 3. Again the same thing, return the number of blocks in my row plus all the blocks that are above my row in the triangle.

Eventually you get to the top row where there is only one block and no rows above it. Hence you don't want to make another recursive call, so you just return the number of blocks in the row, which is one.

So 1 is returned to the method that called it which, in turn returns its number of rows, i.e. 2, plus the 1 that the invoked method returned for a total of three and so on, until you return to the initial invocation.

user_21643650

I'd write it as:

public int triangle(int rows) {
    return (rows <= 0) ? 0 : rows + triangle(rows-1);
}
user_23300530
Related