递推算法及常见示例（C++、Python实现）

递推和递归、迭代的关系简介

在编程里，递推关系可以通过递归或者迭代来实现，但是递归和迭代又不仅仅只能用来实现递推关，有更广泛的用途。

递推（Recurrence）、递归（Recursion）和迭代（Iteration）都是解决问题的方法，它们之间有一定的联系。递归和迭代可以用于实现递推关系，但它们也有各自独立的应用场景。

递推：递推是一种通过重复计算较小的相似子问题来解决较大问题的方法。递推的关键思想是将原问题分解为一系列较小的相似子问题，然后通过计算子问题的解来得到原问题的解。递推通常是指通过已知的初始条件，按照一定的关系式（递推式）逐步推导出问题的解的过程。

递归：递归是一种函数调用自身的技术，通过将问题分解成相似的子问题来解决问题。在递归实现中，函数在其定义中调用自身，这样可以通过重复调用函数来解决问题。递归可以用于实现递推关系。

迭代：迭代是一种重复执行某些操作的方法，通过在每个迭代中更新变量来逐步解决问题。迭代可以用于实现递推关系。迭代通常通过循环结构（如 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   
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   
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   
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 
#include  // 引入 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))

小结：

递推：递推是一种解决问题的方法，它通过已知的初始条件和递推关系（递推式）来逐步构建问题的解。这种方法通常用于数学和算法中，例如在数列或动态规划中。递推不一定涉及函数自我调用，它更多地关注于如何从前一个状态推导出下一个状态。

递归：递归是编程中的一种特殊形式的递推，它涉及到函数调用自身。递归函数通过解决规模更小的子问题来解决原问题，并且通常有一个或多个基本情况，这些情况不需要递归就可以直接解决。递归是一种非常强大的编程技术，可以用来解决各种问题，尤其是那些可以自然分解为相似子问题的问题。

迭代：迭代是通过重复执行一组操作来逐步接近问题解的过程。在编程中，迭代通常通过循环结构实现，如 for 循环或 while 循环。迭代可以用来实现递推关系，通过循环迭代来逐步构建问题的解。

在实际应用中，递归和迭代可以互相转换，但它们的效率可能会有所不同。递归可能会更容易理解和实现，特别是当问题可以自然地分解为子问题时。然而，递归可能会因为函数调用的开销和较大的内存使用而导致性能问题。迭代通常更高效，因为它避免了函数调用的开销，但有时可能不如递归直观。

附、关于递推、递归和迭代更多情况可参见

递推、迭代、递归https://zhuanlan.zhihu.com/p/501040923

递归和迭代介绍及常见示例（C++、Python实现）https://blog.csdn.net/cnds123/article/details/132409886