使用递归的组合函数 c++

Question

下面是组合函数，如果你不知道的话：

C(n,k)= { 1 如果 k=0 或 k = n C(n−1,k−1)+C(n−1,k) 否则

现在，我真正需要的是使用递归来打印帕斯卡三角形。

好的，到目前为止我所做的就是这个简单的递归函数：

#include   <iostream>
using namespace std;

int Pas(int r, int c) {
    if (c == 0 || c == r) {
        return 1;
    } else {
        return Pas(r - 1, c - 1) + Pas(r - 1, c);
    }
}

int main(){

    cout << Pas(4,2) << endl;

    return 0;
}

现在这个函数可以完美地计算例如：

Pas(4,2) = 6

但是我在使用它打印整个 Pascal 三角形时遇到问题，因为我是 C++ 的新手，尤其是递归 ..

非常感谢任何反馈，我希望有人能帮助解决这个问题。但是，如果你们不只是像那样给我整个答案（代码），我将不胜感激；我要学习。

谢谢！

Answer 1

如果允许在循环中使用递归函数，最简单的方法如下：

int n=4; 

for (int i=0; i<=n; i++) {
    for (int j=0; j<=i; j++) {
        cout << Pas(i,j)<<" "; 
    }
    cout <<endl; 
}

如果你想加强排版，你也可以#include <iomanip>和<limits>使用固定大小的数字输出，使用显示整数所需的位数：只需替换输出声明：

    cout << setw(numeric_limits<int>::digits10+1)<<Pas(i,j);

编辑：

您可以轻松构建递归函数来打印三角形的线条：

void PrintPas(int r) {
    if (r==1) 
       cout << Pas(1,0); 
    else {
        PrintPas(r-1);
        for (int c=0; c<=r; c++)
           cout << Pas(r,c)<< " ";
    }
    cout <<endl; 
}

编辑 2

如果你想要一个完全递归的版本：

void PrintPas(int r, int c) {
    if (r==1) 
       cout << Pas(1,0)<<"  "; 
    else if (c==-1) {
        PrintPas(r-1,r-1);
    }
    else {
        PrintPas(r,c-1); 
        cout << Pas(r,c)<< " ";
    }
    if (r==c)
       cout <<endl; 
}

Online demo

Answer 2

与此类似的东西可能适合这份工作

void printTriangle(int printRows, int a = 1, int b = 0)
{
    if (a > printRows) return;
    int val = Pas(a, b);
    cout << val << " ";
    if (a == b) {
        cout << endl;
        printTriangle(printRows, a + 1, 0);
    } else {
        printTriangle(printRows, a, b + 1);
    }
}

运行 printTriangle(7) 应该打印前 7 行。

Answer 3

Tail recursion 是迭代循环的递归等价物。使用 sum(0, 5)

调用时的以下函数

int sum(int start, int end, int resultSoFar = 0) {
    if (start == end) return resultSoFar;
    return sum(start + 1, end, resultSoFar + start);
}

相当于用sum(0, 5).

调用的迭代函数

int sum(int start, int end) {
    int resultSoFar = 0;
    for (int i = start; i < end; i++) {
        resultSoFar += i;
    }
    return resultSoFar;
}

使用递归的组合函数 c++

combinatorial function c++ using Recursion

c++

recursion

using