java - 如何将我的迭代方法更改为递归方法

Question

如何将以下方法从迭代更改为递归？

public int[] pascal(int[] previous) 
{

    //The row is 1 element longer than previous row
    int[] row = new int[previous.length + 1];

    //The first and last numbers in row are always 1
    row[0] = 1;
    row[row.length - 1] = 1;

    //The rest of the row can be calculated based on previous row
    for (int i = 1; i < row.length-1; i++) 
    {
        row[i] = previous[i-1] + previous[i];
    }

    return row;
}

Answer 1

计算的“状态”必须通过参数传递。因此，您需要的参数不仅仅是 int[] previous 行。

通常您需要两种方法，一种是具有更简单接口(interface)的公共(public)方法，另一种是私有(private)方法，后者是实际执行计算的方法。

在您的示例中，这两种方法类似于:

public int[] pascal(int[] previous) { ... call the next overload ... }
private int[] pascal(... all the state needed ...) { ... recursive call or return the value ... }

最直接的方法之一是将正在计算的新行和应计算的下一个位置的索引作为递归函数中的参数传递。所以，你会:

private int[] pascal(int[] previous, int currentIndex, int[] row) { ... }

现在，您的递归函数通常有 2 个(或更多)情况。为此，您将有两种情况:

• 如果“currentIndex”超过了您需要计算的最后一个索引，我们就完成了——只需返回现在的行即可；
• 否则，计算当前索引的值，将其放入行中，然后进行递归调用以继续计算(通过确定计算已完成，或者通过计算并再次调用，... )

让我们对这两种情况进行编码:

private int[] pascal(int[] previous, int currentIndex, int[] row) {
  if (currentIndex == previous.length) {
    return row;
  } else {
    // do some part of the calculation
    // and make a recursive call that would continue the calculation:
    return pascal(previous, ????, row);
  }
}

你明白为什么这是递归函数的结构吗？

好的，开始真正的计算:

private int[] pascal(int[] previous, int currentIndex, int[] row) {
  if (currentIndex == previous.length) {
    return row;
  } else {
    int currentValue = previous[currentIndex - 1] + previous[currentIndex];
    row[currentIndex] = currentValue;
    return pascal(previous, currentIndex, row);
  }
}

计算完成。现在您只需使“更简单”的函数使用适当的参数调用递归函数即可:

public int[] pascal(int[] previous) {
  int rowSize = previous.length + 1;
  int[] row = new int[rowSize];
  row[0] = 1;
  row[rowSize - 1] = 1;
  return pascal(previous, 1, row);
}

就是这样。

如您所见，“技巧”是在参数中保留“状态”。在这里，currentIndex 就像原始 for 循环中的 int i 一样。