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

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

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

来源

2013-02-26 user2109745

是否递归某种作业需求？似乎迭代更简单很多。 – Ryan 2013-02-26 04:21:31

计算的“状态”必须通过参数传递。所以，你需要更多的参数，而不仅仅是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就像您原来的for循环中的int i一样。

来源

2013-02-26 07:09:50

现在已经编程，你必须多次调用该函数才能得到你想要的。

递归函数会自己调用。这样你只需要调用一次就可以得到你想要的东西。

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

想象一下，您已经编制了该功能，您可以将其命名为特定行号N-1。你能写一个函数使用前一个来计算行N吗？

现在只需照顾角落的情况：第一行，也许负数行号。

这就是说，使用这个函数来逐行显示三角形将是非常低效的！

来源

2013-02-26 07:11:00 comocomocomocomo

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

回答

相关问题