递推和递归、迭代的关系简介
在编程里,递推关系可以通过递归或者迭代来实现,但是递归和迭代又不仅仅只能用来实现递推关,有更广泛的用途。
递推、递归和迭代都是解决问题的方法,它们之间有一定的联系。递归和迭代可以用于实现递推关系,但它们也有各自独立的应用场景。
递推:递推是一种通过重复计算较小的相似子问题来解决较大问题的方法。递推的关键思想是将原问题分解为一系列较小的相似子问题,然后通过计算子问题的解来得到原问题的解。递推算法通常使用递归结构来实现。
递归:递归是一种函数调用自身的技术,通过将问题分解成相似的子问题来解决问题。在递归实现中,函数在其定义中调用自身,这样可以通过重复调用函数来解决问题。递归可以用于实现递推关系。
迭代:迭代是一种重复执行某些操作的方法,通过在每个迭代中更新变量来逐步解决问题。迭代可以用于实现递推关系。迭代通常通过循环结构(如 for 循环或 while 循环)实现。
下面是几个简单常见的例子,采用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 = n
f1, f2 = 0, 1
for i in range(2, n+1):
fn = f1 + f2
f1, f2 = f2, fn
print("斐波那契数列的第 {} 项为:{}".format(n, fn))
下面改用使用自定义函数实现:
def fibonacci(n):
if n <= 1:
return n
f1, 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) * d
print("等差数列的前 {} 项和为:{}".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://zhuanlan.zhihu.com/p/501040923
递归和迭代介绍及常见示例(C++、Python实现)https://blog.csdn.net/cnds123/article/details/132409886