数学问题求解——算法系列教程(c++版)
梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）
递归在数学问题中应用极广，因为阶乘、斐波那契、组合 / 排列数 这类数学公式本身就具备「递归定义」的特征，用递归实现的代码简洁易懂、逻辑和数学公式完全一致，非常适合入门学习递归的核心用法。以下是 4 个典型实例：
递归核心要素
- 递归公式（递推关系）：数学问题的递归定义式，描述「大问题」和「小问题」的关系，比如 n! = n × (n-1)! 、f(n) = f(n-1) + f(n-2)
- 递归终止条件：递归的「出口」，当问题规模小到可以直接得出答案时，停止递归，防止无限递归（栈溢出），比如 0! = 1、f(0)=0, f(1)=1
教程目录导航
▼
一、阶乘计算
问题描述：
- 对于非负整数 n，阶乘的定义如下：n! = n × (n-1) × (n-2) × ... × 1 特殊值：0! = 1 ，1! = 1
算法解析：
- 递归公式：n! = n × (n-1)!
- 终止条件：n=0 时，返回 1
#include <iostream>
using namespace std;
// 迭代计算n的阶乘
long long factorial_iter(int n) {
long long sum =1;
for(int i=n;i>0;i--) {
sum = sum * i;
}
return sum;
}
// 递归计算n的阶乘
long long factorial_recu(int n) {
// 1. 递归终止条件（基准条件）
if (n == 0) {
return 1;
}
// 2. 递归公式：大问题拆解为小问题
return n * factorial_recu(n - 1);
}
int main() {
int n;
cout << "请输入一个非负整数n：";
cin >> n;
if (n < 0) {
cout << "错误：阶乘仅支持非负整数！" << endl;
} else {
cout << "迭代计算" << n << "! = " << factorial_iter(n) << endl;
cout << "递归计算" << n << "! = " << factorial_recu(n) << endl;
}
return 0;
}
输出结果
请输入一个非负整数n：5
迭代计算5! = 120
递归计算5! = 120
二、斐波那契数列(Fibonacci)
斐波那契数列---这个数列从第三项开始,每一项都等于前两项之和。
斐波那契数列是递归的经典应用，也是动态规划的前置案例，能直观看到递归的优缺点。
问题描述：
- F(0)=0
- F(1)=1
- F(n) = F(n-1) + F(n-2) (n >= 2)
数列：0, 1, 1, 2, 3, 5, 8, 13, 21, ...
算法解析：
- 递归公式：F(n) = F(n-1) + F(n-2)
- 终止条件：n=0 返回 0，n=1 返回 1
#include <iostream>
using namespace std;
// 迭代计算斐波那契数列第n项(动态规划)
long long fibonacci_iter(int n) {
long long up1 =0;
long long up2 =1;
long long sum =0;
for(int i=2; i <= n; i++) {
sum = up1 + up2;
//更新前两项
up1 = up2;
up2 = sum;
}
if(n == 0) sum = up1;
if(n == 1) sum = up2;
return sum;
}
// 递归计算斐波那契数列第n项
long long fibonacci_recu(int n) {
// 1. 递归终止条件
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
// 2. 递归公式
return fibonacci_recu(n - 1) + fibonacci_recu(n - 2);
}
int main() {
int n;
cout << "请输入斐波那契数列的项数n：";
cin >> n;
if (n < 0) {
cout << "错误：项数不能为负数！" << endl;
} else {
cout << "迭代计算斐波那契数列第" << n << "项 = " << fibonacci_iter(n) << endl;
cout << "递归计算斐波那契数列第" << n << "项 = " << fibonacci_recu(n) << endl;
}
return 0;
}
输出结果
请输入斐波那契数列的项数n：10
迭代计算斐波那契数列第10项 = 55
递归计算斐波那契数列第10项 = 55
三、组合数计算 C $\binom{k}{n}$
问题描述：
- 组合数：从 n 个不同元素中，取出 k 个元素的不考虑顺序的组合个数，记为 C$\binom{k}{n}$
- 示例1：从 5 个不同元素中，取出 3 个元素的不考虑顺序的组合个数？
算法解析：
- 算法一：C$\binom{k}{n}$=$\frac {n!} {k!×(n-k)!}$
- 解：C$\binom{3}{5}$=$\frac {5!} {3!×(5-3)!}$=$\frac {5×4×3×2×1} {(3×2×1)×(2×1)}$=$\frac {20} {2}$=10
- 迭代实现
- 阶乘部分采用迭代实现：factorial_iter(n) / ( factorial_iter(k) * ( factorial_iter(n - k) ) )
- 递归实现
- 阶乘部分采用递归实现：factorial_recu(n) / ( factorial_recu(k) * ( factorial_recu(n - k) ) )
- 算法二：C$\binom{k}{n}$= C$\binom{k-1}{n-1}$+C$\binom{k}{n-1}$ 杨辉三角
- 解：C$\binom{3}{5}$=C$\binom{3-1}{5-1}$+C$\binom{3}{5-1}$=C$\binom{2}{4}$+C$\binom{3}{4}$=$\frac {4!} {2!×(4-2)!}$+$\frac {4!} {3!×(3-2)!}$=$\frac {4×3×2×1} {(2×1)×(2×1)}$+$\frac {4×3×2×1} {(3×2×1)×(1×1)}$=6+4=10
- 递归实现
- 递归公式：C(n,k)=C(n−1,k−1)+C(n−1,k)
从 n 个元素中选 k 个，分为两种情况：
- 选第 n 个元素：则需要从剩下的 n-1 个元素中选 k-1 个 → C(n-1,k-1)；
- 不选第 n 个元素：则需要从剩下的 n-1 个元素中选 k 个 → C(n-1,k)；
- 终止条件：3个
- C(n,0) = 1：从 n 个元素中选 0 个，只有 1 种选法（什么都不选）；
- C(n,n) = 1：从 n 个元素中选 n 个，只有 1 种选法（全选）；
- C(n,k) = 0：当 k > n 时，无意义，返回 0。
- 递归公式：C(n,k)=C(n−1,k−1)+C(n−1,k)
- 迭代实现
- 生成杨辉二维数组：公式 C(n,k) = C(n-1,k-1) + C(n-1,k)
- 从二维数组成选取n行k列的值
- 算法三：直接乘积法
- 迭代实现
- 利用组合数对称性 C$\binom{k}{n}$ = C$\binom{n-k}{n}$，选较小的数计算，减少循环次数。
- 比如 C$\binom{8}{10}$ = C$\binom{2}{10}$，只需要循环2次而非8次。
- 解：C$\binom{8}{10}$=$\frac {10!} {8!×(10-8)!}$=$\frac {10×9×8×7×6×5×4×3×2×1} {(8×7×6×5×4×3×2×1)×(2×1)}$=$\frac {90} {2}$=45
- 解：C$\binom{2}{10}$=$\frac {10!} {2!×(10-2)!}$=$\frac {10×9×8×7×6×5×4×3×2×1} {(2×1)×(8×7×6×5×4×3×2×1)}$=$\frac {90} {2}$=45
- 比如 C$\binom{3}{5}$ = C$\binom{2}{5}$，只需要循环2次而非3次。
- 解：C$\binom{3}{5}$=$\frac {5!} {3!×(5-3)!}$=$\frac {5×4×3×2×1} {(3×2×1)×(2×1)}$=$\frac {20} {2}$=10
- 解：C$\binom{2}{5}$=$\frac {5!} {2!×(5-2)!}$=$\frac {5×4×3×2×1} {(2×1)×(3×2×1)}$=$\frac {20} {2}$=10
- 比如 C$\binom{8}{10}$ = C$\binom{2}{10}$，只需要循环2次而非8次。
- 组合数公式变形：C$\binom{k}{n}$=$\frac {n!} {k!×(n-k)!}$=1×$\frac {n-k+1} {1}$×$\frac {n-k+2} {2}$...×$\frac {n-k+k} {k}$
- 解：C$\binom{3}{5}$=1×$\frac {5-3+1} {1}$×$\frac {5-3+2} {2}$×$\frac {5-3+3} {3}$=10
- 解：C$\binom{2}{5}$=1×$\frac {5-2+1} {1}$×$\frac {5-2+2} {2}$=10
- 核心代码：
- k = min(k, n - k); //选较小的数计算
- res = res * (n - k + i) / i; // 迭代推进
- 利用组合数对称性 C$\binom{k}{n}$ = C$\binom{n-k}{n}$，选较小的数计算，减少循环次数。
- 迭代实现
#include <iostream>
using namespace std;
// 迭代计算n的阶乘
long long factorial_iter(int n) {
long long sum =1;
for(int i=n;i>0;i--) {
sum = sum * i;
}
return sum;
}
// 递归计算n的阶乘
long long factorial_recu(int n) {
// 1. 递归终止条件（基准条件）
if (n == 0) {
return 1;
}
// 2. 递归公式：大问题拆解为小问题
return n * factorial_recu(n - 1);
}
// 迭代计算组合数（杨辉三角）
long long combination_iter(int n, int k) {
// 边界条件：非法输入返回0
if (k < 0 || k > n) return 0;
if (k == 0 || k == n) return 1;
// 创建二维数组存储杨辉三角，dp[i][j] 表示 C(i,j)
vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
// 初始化第0行
dp[0][0] = 1;
// 迭代生成每一行
for (int i = 1; i <= n; ++i) {
dp[i][0] = 1; // 每行第一个数为1
dp[i][i] = 1; // 每行最后一个数为1
// 计算中间的数
for (int j = 1; j < i; ++j) {
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}
}
return dp[n][k];
}
// 递归计算组合数（杨辉三角）
long long combination_recu(int n, int k) {
// 1. 递归终止条件
if (k == 0 || k == n) {
return 1;
}
if (k > n) {
return 0;
}
// 2. 递归公式：C(n,k) = C(n-1,k-1) + C(n-1,k)
return combination_recu(n - 1, k - 1) + combination_recu(n - 1, k);
}
// 迭代计算组合数（直接乘积法）
long long combination_product(int n, int k) {
if (k < 0 || k > n) return 0;
if (k == 0 || k == n) return 1;
k = min(k, n - k);
// 优化计算：直接计算乘积形式，避免阶乘
long long res = 1;
for (int i = 1; i <= k; ++i) {
// 分步乘除，避免中间结果溢出（比如先乘 n-k+i，再除以 i）
res = res * (n - k + i) / i;
}
return res;
}
int main() {
int n, k;
cout << "请输入n和k（计算C(n,k)）：";
cin >> n >> k;
if (n < 0 || k < 0) {
cout << "错误：n和k必须为非负整数！" << endl;
} else {
cout << "算法一迭代实现：C(" << n << "," << k << ") = " << factorial_iter(n) / ( factorial_iter(k) * ( factorial_iter(n - k) ) ) << endl;
cout << "算法一递归实现：C(" << n << "," << k << ") = " << factorial_recu(n) / ( factorial_recu(k) * ( factorial_recu(n - k) ) ) << endl;
cout << "算法二迭代实现：C(" << n << "," << k << ") = " << combination_iter(n, k) << endl;
cout << "算法二递归实现：C(" << n << "," << k << ") = " << combination_recu(n, k) << endl;
cout << "算法三迭代实现：C(" << n << "," << k << ") = " << combination_product(n, k) << endl;
}
return 0;
}
输出结果
请输入n和k（计算C(n,k)）：5 3
算法一迭代实现：C(5,3) = 10
算法一递归实现：C(5,3) = 10
算法二迭代实现：C(5,3) = 10
算法二递归实现：C(5,3) = 10
四、排列数计算 A $\binom{k}{n}$
问题描述：
- 排列数：从 n 个不同元素中，取出 k 个元素的考虑顺序的排列个数，记为 A $\binom{k}{n}$
- 比如：从 {1,2,3} 中选 2 个，排列是 (1,2)、(2,1)、(1,3)、(3,1)、(2,3)、(3,2)（共 6 种）。
算法解析：
- 算法一：A$\binom{k}{n}$=$\frac {n!} {(n-k)!}$
- 解：A$\binom{2}{3}$=$\frac {3!} {(3-2)!}$=$\frac {3×2×1} {(1×1)}$=$\frac {6} {1}$=6
- 迭代实现
- 阶乘部分采用迭代实现：factorial_iter(n) / factorial_iter(n - k)
- 递归实现
- 阶乘部分采用递归实现：factorial_recu(n) / factorial_recu(n - k)
- 算法二：直接乘积法
- 递归实现
- 递归公式：A $\binom{k}{n}$=n×A(n−1,k−1)
- 从 n 个元素中选 m 个排列
- 第一步先选第一个位置的元素，有 n 种选择；
- 第二步从剩下的 n-1 个元素中选 k-1 个排列，有A(n-1,m-1)种选择，两者相乘就是总排列数。
- 终止条件: 2 个
- A(n,0) = 1：选 0 个元素，只有 1 种排列方式；
- A(n,k) = 0：当 k > n 时，无意义，返回 0。
- 递归公式：A $\binom{k}{n}$=n×A(n−1,k−1)
- 迭代实现
- 排列数公式变形：A$\binom{k}{n}$=$\frac {n!} {(n-k)!}$ = n * (n-1) * ... (n-k+1)
- 解：A$\binom{2}{3}$=$\frac {3!} {(3-2)!}$= 3 * (3-1) = 6
- 解：A$\binom{3}{5}$=$\frac {5!} {(5-3)!}$= 5 * (5-1) * (5-2) = 60
- 核心代码：
- res = res * (n - i); // 迭代推进
- 递归实现
#include <iostream>
using namespace std;
// 迭代计算n的阶乘
long long factorial_iter(int n) {
long long sum =1;
for(int i=n;i>0;i--) {
sum = sum * i;
}
return sum;
}
// 递归计算n的阶乘
long long factorial_recu(int n) {
// 1. 递归终止条件（基准条件）
if (n == 0) {
return 1;
}
// 2. 递归公式：大问题拆解为小问题
return n * factorial_recu(n - 1);
}
// 迭代计算排列数 A(n,k)
long long permutation_iter(int n, int k) {
if (k < 0 || k > n) return 0;
if (k == 0) return 1;
long long res = 1;
// 递进计算：n*(n-1)*...*(n-k+1)
for (int i = 0; i < k; ++i) {
res = res * (n - i);
}
return res;
}
// 递归计算排列数 A(n,k)
long long permutation_recu(int n, int k) {
// 1. 递归终止条件
if (k == 0) {
return 1;
}
if (k > n) {
return 0;
}
// 2. 递归公式
return n * permutation_recu(n - 1, k - 1);
}
int main() {
int n, k;
cout << "请输入n和k（计算A(n,k)）：";
cin >> n >> k;
if (n < 0 || k < 0) {
cout << "错误：n和k必须为非负整数！" << endl;
} else {
cout << "算法一迭代实现：A(" << n << "," << k << ") = " << factorial_iter(n) / factorial_iter(n - k) << endl;
cout << "算法一递归实现：A(" << n << "," << k << ") = " << factorial_recu(n) / factorial_recu(n - k) << endl;
cout << "算法二迭代实现：A(" << n << "," << k << ") = " << permutation_iter(n, k) << endl;
cout << "算法二递归实现：A(" << n << "," << k << ") = " << permutation_recu(n, k) << endl;
}
return 0;
}
输出结果
请输入n和m（计算A(n,k)）：5 2
算法一迭代实现：(5,2) = 20
算法一递归实现：(5,2) = 20
算法二迭代实现：(5,2) = 20
算法二递归实现：(5,2) = 20
五、总结
结合本文的 4 个数学实例，总结递归在求解数学问题时的优缺点
优点
- 代码极简，逻辑和数学公式完全一致：递归代码的写法几乎就是数学公式的直译，比如阶乘的n! = n*(n-1)!，递归代码就是n*factorial(n-1)，极易理解和编写；
- 无需手动维护循环变量：数学问题的循环实现需要手动控制循环次数和变量更新，递归自动处理，代码更简洁；
- 天然适配数学递归定义：阶乘、斐波那契、组合 / 排列数这类数学问题本身就是递归定义的，递归是「最优解」。
缺点
- 存在重复计算：如未优化的斐波那契，会重复计算大量子问题，效率偏低；
- 栈溢出风险：递归调用会占用函数栈，当 n 过大（比如 n=10000）时，会触发栈溢出错误；
- 空间开销略大：递归的栈空间开销比循环大。
在数学问题中，优先使用递归的场景：
- 问题的数学定义是递归形式的；
- 数据规模不大（不会导致栈溢出）；
- 追求代码的简洁性和可读性。
返回顶部