递归法求组合数

递归法求组合数的基本思路是利用组合数的递推公式C(n,m)=C(n-1,m)+C(n-1,m-1)进行递归求解。具体实现可以采用以下伪代码：

function C(n, m):
    if m == 0 or m == n:
        return 1
    else:
        return C(n-1, m) + C(n-1, m-1)

上述代码中，如果m等于0或者等于n，则返回1；否则，利用递推公式求解C(n,m)。递归终止条件是m等于0或者等于n，这是因为C(n,0)和C(n,n)都等于1。

需要注意的是，递归法求组合数的时间复杂度高，存在大量的重复计算，因此在实际应用中不太实用。可以采用动态规划等其他方法进行优化。

相关问题

使用C++编写一段程序，用递归法求组合数

好的，下面是使用C++编写的递归法求组合数的程序：

#include <iostream>
using namespace std;

int C(int n, int m) {
    if (m == 0 || m == n) {
        return 1;
    } else {
        return C(n-1, m) + C(n-1, m-1);
    }
}

int main() {
    int n, m;
    cout << "请输入n和m的值（n>=m）：" << endl;
    cin >> n >> m;
    cout << "C(" << n << "," << m << ")=" << C(n, m) << endl;
    return 0;
}

在上述代码中，我们定义了一个C函数，用于递归求解组合数。在主函数中，我们首先输入n和m的值，然后调用C函数求解组合数，并输出结果。

需要注意的是，上述代码中并没有对输入的n和m进行合法性检查，因此在实际应用中需要进行相应的判断。

c++：：用递归法求组合数。 （1）主函数功能：从键盘输入n和m，通过调用子函数计算组合数并输出。 （2）子函数功能：使用递归法，计算组合数。

好的，我可以帮你解答这个问题。下面是c++的代码实现：

#include <iostream>

using namespace std;

int combination(int n, int m) {
    if (m == 0 || m == n) {
        return 1;
    } else {
        return combination(n - 1, m - 1) + combination(n - 1, m);
    }
}

int main() {
    int n, m;
    cout << "请输入n和m：" << endl;
    cin >> n >> m;
    cout << "组合数为：" << combination(n, m) << endl;
    return 0;
}

在这个程序中，combination函数使用了递归法来计算组合数。如果m等于0或n等于m，那么组合数为1；否则，组合数为C(n-1,m-1) + C(n-1,m)。主函数中从键盘输入n和m，调用combination函数计算组合数并输出。