0

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

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

2 回答 2

1

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

通常你希望有 2 种方法，一种是具有更简单接口的公共方法，另一种是私有方法，它是实际执行计算的方法。

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

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就像int i在您的原始for循环中一样。

于 2013-02-26T07:09:50.580 回答
0

由于它现在已编程，您必须多次调用该函数才能获得所需的内容。

递归函数会调用自己。这样，您只需调用一次即可获得所需的内容。

我想你只想要三角形的一个特定行。您需要传递给函数的唯一参数是行号。

想象一下，您已经编写了该函数，并且可以为特定的行号 N-1 调用它。你能写一个使用前一个函数来计算第 N 行的函数吗？

现在只需处理极端情况：第一行​​和可能的负行数。

也就是说，使用此函数逐行显示三角形将非常低效！

于 2013-02-26T07:11:00.400 回答