java - 递归无法做到这一点

Question

我们有由块组成的三角形。最上面一行有 1 个块，下一行有 2 个块，下一行有 3 个块，以此类推。递归计算（无循环或乘法）具有给定行数的此类三角形中的块总数。

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

这是我的代码：

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

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

Answer 1

在编写简单的递归函数时，将其拆分为“基本情况”（停止时）和递归时的情况会有所帮助。两种情况都需要返回一些东西，但递归情况会在某个时候再次调用该函数。

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

如果您进一步研究递归定义，您会发现“尾递归”的想法，这通常是最好的，因为它允许某些不会溢出堆栈的编译器优化。我的代码示例虽然简单正确，但不是尾递归的。

Answer 2

您没有使用函数的返回值。相反，您总是声明一个新的局部变量。否则，您的解决方案非常接近正确的解决方案。return此外，如果您不在第 0 行，您还应该添加另一个。

Answer 3

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