递推算法及常见示例（C++、Python实现）
递推算法及常见示例（C++、Python实现）
递推算法是一种用若干步可重复运算来描述复杂问题的方法，它是一种序列计算中的常用算法。通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。递推关系通常表示为一种递推公式。
下面是一些常见的例子。
★斐波那契数列：斐波那契数列指的是这样一个数列：0，1，1，2，3，5，8，13，21，34，55，89...
这个数列从第3项开始，每一项都等于前两项之和。
斐波那契数列是一种经典的递推问题，它的定义是：f(0)=0，f(1)=1，f(n)=f(n-1)+f(n-2)。通过这个递推关系式，可以求解斐波那契数列的第 n 项。
☆C++实现：
#include <iostream>
using namespace std; int main() { int n; cout << "请输入项数 n 的值： "; cin >> n; if (n <= 1) { return n; } int f1 = 0, f2 = 1, fn; for (int i = 2; i <= n; i++) { fn = f1 + f2; f1 = f2; f2 = fn; } cout << "斐波那契数列的第 " << n << " 项为：" << fn << endl; return 0;
}
下面改用使用自定义函数实现：
#include <iostream>
using namespace std; int fibonacci(int n) { if (n <= 1) { return n; } int f1 = 0, f2 = 1, fn; for (int i = 2; i <= n; i++) { fn = f1 + f2; f1 = f2; f2 = fn; } return fn;
} int main() { int n; cout << "请输入项数 n 的值： "; cin >> n; cout << "斐波那契数列的第 " << n << " 项为：" << fibonacci(n) << endl; return 0;
}
☆Python实现：
n = int(input("请输入 n 的值："))
if n <= 1: fn = nf1, f2 = 0, 1 for i in range(2, n+1): fn = f1 + f2 f1, f2 = f2, fnprint("斐波那契数列的第 {} 项为：{}".format(n, fn))
下面改用使用自定义函数实现：
def fibonacci(n): if n <= 1: return nf1, f2 = 0, 1 for i in range(2, n+1): fn = f1 + f2 f1, f2 = f2, fn return fn n = int(input("请输入 n 的值："))
print("斐波那契数列的第 {} 项为：{}".format(n, fibonacci(n)))
★等差数列求和： 1, 3, 5, 7, 9 是一个公差为 2 的等差数列。等差数列的求和问题可以通过递推算法解决。设等差数列的首项为 a1，公差为 d，第 n 项为 an，则 an=a1+(n-1)d。要求等差数列的前 n 项和，可以递推得到：Sn=a1+a2+...+an=n/2[2a1+(n-1)d]。
☆C++实现：
#include <iostream>
using namespace std;int main() { int a1, d, n; cout << "输入第一项、公差和项数："; cin >> a1 >> d >> n; int sum = 0; for (int i = 1; i <= n; i++) { sum += a1 + (i - 1) * d; } cout << "等差数列的前 " << n << " 项和为：" << sum << endl; return 0;
}
☆Python实现：
a1 = int(input("输入第一项: "))
d = int(input("输入公差: "))
n = int(input("输入项数: "))
sum = 0
for i in range(1, n+1): sum += a1 + (i - 1) * dprint("等差数列的前 {} 项和为：{}".format(n,sum))★等比数列求和：1, 2, 4, 8, 16 是一个公比为 2 的等比数列。等比数列的求和问题也可以通过递推算法解决。设等比数列的首项为 a1，公比为 r，第 n 项为 an，则 an=a1r^(n-1)。要求等比数列的前 n 项和，可以递推得到：Sn=a1(1-r^n)/(1-r)。
☆C++实现：
#include <iostream>
#include <cmath> // 引入 pow()
using namespace std;int main() { double a1, r, n; cout << "输入第一项、公比和项数："; cin >> a1 >> r >> n; double sum = 0; for (int i = 1; i <= n; i++) { sum += a1 * pow(r, i - 1); } cout << "等比数列的前 " << n << " 项和为：" << sum << endl; return 0;
}
☆Python实现：
a1 = float(input("输入第一项："))
r = float(input("输入公比："))
n = int(input("输入项数：")) sum = 0
for i in range(1, n + 1): sum += a1 * (r ** (i - 1)) print("等比数列的前 {} 项和为：{}".format(n, sum))
附、递推、递归和迭代区别
递推是通过已知序列元素来计算其他元素，递归是函数调用自身，迭代是通过重复执行操作来解决问题。
递归和迭代可参见：https://blog.csdn.net/cnds123/article/details/132409886