我正在寻找关于帕斯卡三角的递归版本如何工作的解释
以下是帕斯卡三角形的递归返回线。
int get_pascal(const int row_no,const int col_no)
{
if (row_no == 0)
{
return 1;
}
else if (row_no == 1)
{
return 1;
}
else if (col_no == 0)
{
return 1;
}
else if (col_no == row_no)
{
return 1;
}
else
{
return(get_pascal(row_no-1,col_no-1)+get_pascal(row_no-1,col_no));
}
}
我知道算法是如何工作的 我想知道的是递归是如何工作的。
您的算法包含几个不必要的基本情况谓词。可以更简单地表述如下：
int pascal(int row, int col) {
if (col == 0 || col == row) {
return 1;
} else {
return pascal(row - 1, col - 1) + pascal(row - 1, col);
}
}
这当然假设您保证传递给函数的参数是非负整数；如果你不能从函数外部强加这样的保证，你总是可以包含一个断言。
帕斯卡三角形本质上是紧接在它上面的两个值的总和......
1
1 1
1 2 1
1 3 3 1
ETC
对于这两个边界条件，我们在特殊情况下进行编码（用于初始化）。代码的主要部分（递归部分）是实际的逻辑。
（条件'row == 1'不是必需的）
最优化的方法是这个：
int pascal(int row, int col) {
if (col == 0 || col == row) return 1;
else if(col == 1 || (col + 1) == row) return row;
else return pascal(row - 1, col - 1) + pascal(row - 1, col);
}
与 Fox 的算法不同，它可以防止递归调用可以从输入值轻松计算的值。
源代码参考页面：
#include <stdio.h>
int main()
{
int n, x, y, c, q;
printf("Pascal Triangle Program\n");
printf("Enter the number of rows: ");
scanf("%d",&n);
for (y = 0; y < n; y++)
{
c = 1;
for(q = 0; q < n - y; q++)
{
printf("%3s", " ");
}
for (x = 0; x <= y; x++)
{
printf(" %3d ",c);
c = c * (y - x) / (x + 1);
}
printf("\n");
}
printf("\n");
return 0;
}
输出将是，
帕斯卡三角计划
输入行数：11
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
帕斯卡三角形可以通过将两个条目添加到当前条目之上来获得。
| 0 1 2 3 列 --+---------------------------------------------- 0 | 1个（案例1） 1 | 1（案例 2） 1（案例 2） 2 | 1（案例 3） 2（总和） 1（案例 4） 3 | 1（案例 3） 3（总和） 3（总和） 1（案例 4） 排
等，例如第2列第3行=第2列第2行+第1列第2行，其中情况如下：
if (row_no == 0) // case 1
{
return 1;
}
else if (row_no == 1) // case 2
{
return 1;
}
else if (col_no == 0) // case 3
{
return 1;
}
else if (col_no == row_no) // case 4
{
return 1;
}
else // return the sum
return pascalRecursive(height-1,width)+pascalRecursive(height-1,width-1);
这是@kathir-softwareandfinance的代码， 具有更易读和更有意义的变量名
#include <stdio.h>
int main()
{
int nOfRows, cols, rows, value, nOfSpace;
printf("Pascal Triangle Program\n");
printf("Enter the number of rows: ");
scanf("%d",&nOfRows);
for (rows = 0; rows < nOfRows; rows++)
{
value = 1;
for(nOfSpace = 0; nOfSpace < nOfRows - rows; nOfSpace++)
{
printf("%3s", " ");
}
for (cols = 0; cols <= rows; cols++)
{
printf(" %3d ",value);
value = value * (rows - cols) / (cols + 1);
}
printf("\n");
}
printf("\n");
return 0;
}
这是递归的工作原理
We call v(i, j), it calls v(i - 1, j), which calls v(i - 2, j) and so on,
until we reach the values that are already calculated (if you do caching),
or the i and j that are on the border of our triangle.
Then it goes back up eventually to v(i - 1, j), which now calls v(i - 2, j - 1),
which goes all the way to the bottom again, and so on.
....................................................................
_ _ _ _ call v(i, j) _ _ _ _ _
/ \
/ \
/ \
call v(i - 1, j) v(i - 1, j - 1)
/ \ / \
/ \ / \
call v(i - 2, j) v(i - 2, j - 1) v(i - 2, j - 1) v(i - 2, j - 2)
....................................................................
如果您需要经常获取该值，并且您有足够的内存：
class PascalTriangle
# unlimited size cache
public
def initialize
@triangle = Array.new
end
def value(i, j)
triangle_at(i, j)
end
private
def triangle_at(i, j)
if i < j
return nil
end
if @triangle[i].nil?
@triangle[i] = Array.new(i + 1)
else
return @triangle[i][j]
end
if (i == 0 || j == 0 || i == j)
@triangle[i][j] = 1
return @triangle[i][j]
end
@triangle[i][j] = triangle_at(i - 1, j) + triangle_at(i - 1, j - 1)
end
end
使用三元方法进行优化；只需要 1 个返回命令。
int f(int i, int j) {
return (
(i <= 1 || !j || j == i) ? 1 :
(f(i - 1, j - 1) + f(i - 1, j))
);
}
看解释