java - 使用不带循环和乘法的递归调用来查找值

Question

考虑这个问题:

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.

我解决这个问题的方法是这样的

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

对于数字 3 以内的值，程序可以正常工作，但是应该输出的值是错误的(计算错误/递归调用)。我错过了什么？

提前谢谢您!

Answer 1

你的想法是对的。您从“底部”行开始，在每次递归调用中，您移动到上面的行，直到到达顶行，其中仅包含一个 block 。您唯一的问题是您需要添加行数，而不是添加 2。
(代码后面有说明。)

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);
    }
}

让我们举一个简单的示例，您最初使用值为 4 调用方法 triangle()。这意味着底行包含四个 block ，上面的行包含三个 block 。所以上面代码中最后一个return语句的意思是:
返回我的行中的 block 数加上三角形中我的行上方的所有 block 。

因此，triangle() 方法使用值 3 调用自身。同样，返回我所在行中的 block 数以及三角形中我的行上方的所有 block 数。

最终你到达顶行，那里只有一个 block ，上面没有行。因此，您不想进行另一次递归调用，因此只需返回该行中的 block 数，即 1。

因此，1 被返回到调用它的方法，该方法又返回其行数，即 2，加上被调用方法返回的 1，总共 3 依此类推，直到返回到初始调用.