一、递推算法:
递推算法是一种顺序递推的数学关系模型算法，好比通项公式。在数值计算的过程之中，只需要知道递推的边界值(一般是初值)，也就是最开始的原始数值，然后类推，直到求出第n项数值，也就是目标值为终点。
二、递归算法:
递归算法：在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归算法实际上是一种调用自己的一种函数(递归函数)，它往往从结果出发，每一次函数的调用都是从函数结果和当前传入值相关，然后再顺着函数结果的下一个函数结果和当前函数的传入值再次计算，直到最终破除这个调用的界限，即函数结果最终返回的是一个确定的值而不再是这个函数结果的本身调用。
三、递推算法和递归算法的区别：
1、算法的过程不同
递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。
递归算法在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。
2、递推与递归的比较相对于递归算法，递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发，直到求出函数值。
3、两种算法用途不同
递归算法绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言中习惯用递归来实现循环。
而递推算法是给定一个数的序列x₀,x₁,…,xₙ,…若存在整数n0，使当n>n₀时,可以用等号(或大于号、小于号)将xₙ与其前面的某些项xᵢ(0<i<n)联系起来，这样的式子就叫做递推关系。
四、递推算法的特点
一个问题的求解需要大量重复计算，在已知的条件和所求问题之间总存在着某种相互联系的关系，在计算时，我们需要找到这种关系，进行计算(递推关系式)。
递推法的关键，就是找到递推关系式，这种处理方式能够将复杂的计算过程，转化为若干步骤的简单重复运算，充分利用计算机运行程序时的时间局部性和空间局部性。
递推算法的思想：
- 首要问题是先找到各个相邻数据项之间的递推关系；
- 递推关系避开了求通项公式的麻烦，且有些题目的通项公式很难求，或者不能进行求解；
- 将复杂问题分解为若干步骤的简单运算；
- 一般来说递推算法就是一种特殊的迭代算法。
递推算法解题的基本思路：
- 将复杂计算转换为简单重复运算；
- 通过找到递推关系式进行简化运算；
- 利用计算机的特性，减少运行时间。
递推算法的一般步骤：
- 根据题目确定数据项，并找到符合要求的递推关系式；
- 根据递推关系式设计递推程序；
- 根据题目找到递推的终点；
- 单次查询可以不进行存储，多次查询都要进行存储；
- 按要求输出答案即可。
五、递归算法的特点
递归算法是一种从自顶向下的算法，实际上是通过不停的直接调用或者间接的调用自身的函数，通过每次改变变量完成多个过程的重复计算，直到到达边界之后，结束调用。
与递推法相似的是，递归与递推都是将一个复杂过程分解为几个简单重复步骤进行计算。
递归算法的实现的核心是分治策略，即分而治之，将复杂过程分解为规模较小的同类问题，通过解决若干个小问题，进而解决整个复杂问题
递归算法的思想：
- 将复杂计算过程转换为简单重复子过程；
- 找到递归公式，即能够将大问题转化为小问题的公式；
- 自上而下计算，在返回完成递归过程。
- 递归算法设计的一般步骤：
- 根据题目设计递归函数中的运算部分；
- 根据题目找到递归公式，题目可能会隐含给出，也可能需要自己进行推导；
- 找到递归出口，即递归的终止条件。
六、案例
例1 π是数学和物理学普遍使用的常数之一，它定义了圆周长与直径之比，但π是一个无理数，即无限不循环小数，n值无法用任何精确公式表示，请用(格雷戈里-莱布尼茨(Gregory–Leibniz)级数求π的近似值。
解：
德国数学家莱布尼茨(Leibniz)于1674年曾提出Gregory-Leibniz公式为
用递推算法求π：
# 递推算法计算
n0 = 200000 # 求和的项数
π = 0 # 设置π初值(求和初值为0)
n = 1 # 计数值，即公式中的n
f = 1 # 符号，第1项为正，以后每次乘以-1，实现正负交替，比(-1)ⁿ⁻¹快
while n <= n0:
gl = 4/(2*n-1) # 递推式
π += f*gl # 第前n项和
n += 1
f = -f # 正负符号取反，相当于(-1)ⁿ⁻¹
print(f'π={π:.5f}')执行结果：
π=3.14159
用递归算法求π：
# 递归算法计算
n0 = 1000 # 求和的项数。Python默认递归深度为1000
def pi(n):
f = -1 if n % 2 == 0 else 1 # n为偶数f=-1，奇数f=1。即(-1)ⁿ⁻¹
if n == 1:
return 4 # 递归结束条件
return 4*f/(2*n-1)+pi(n-1) # 递归调用
print(f'π={pi(n0):.5f}')执行结果：
π=3.14059
由于Gregory-Leibniz级数收敛很慢，200000次也仅达到10⁻⁵的精度，1000次精度仅10⁻²。
例2 一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积，并且0的阶乘为1(0!=1)。自然数n的阶乘写作n!，即n!=1×2×3×…×n。编写程序，计算n的阶乘。
用递推算法求阶乘：
# 递推求n!=1×2×3×…×n
n = int(input('请输入一个正整数：')) # 求n阶乘
if n < 0: n = -n # 负数转正数(负数无阶乘)
f = 1 # 连乘初值为1
for i in range(1,n+1): # 循环n次，n=0进不了循环，值f=1
f *= i
print(f'{n}!={f}') # 输出结果执行结果：
用递归算法求阶乘：
# 递归求n!=1×2×3×…×n
def factorial(n):
if n<= 1:
return 1 # 0和1的阶乘都为1，返回结果并退出
return n*factorial(n-1) # 递归调用，n!=n*(n-1)!
n = int(input('请输入一个正整数：')) # 求n阶乘
if n < 0: n = -n # 负数转正数(负数无阶乘)
print(f'{n}!={factorial(n)}') # 调用函数返回结果执行结果：
例3 斐波那契数列(Fibonacci sequence)，又称黄金分割数列，因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n – 1)+F(n – 2)(n > 2，n ∈ N*)。也就是说：斐波那契数列第1项为1，第2项为1，从第3项起为前2项之和。
用递推算法求斐波那契数列
# 用递推算法求斐波那契数列
n = int(input('请输入一个正整数：')) # 求第n项
a = 1 # 第1项
b = 1 # 第2项
for i in range(3, n+1):
a, b = b, a + b # a前一项，b为当前项
print(f'Fib({n})={b}') # 输出结果执行结果：
用递归算法求斐波那契数列
# 用递归算法求斐波那契数列
def fib(n):
if n<3:
return 1
return fib(n-1) + fib(n-2)
n = int(input('请输入一个正整数：')) # 求第n项
print(f'Fib({n})={fib(n)}') # 调用函数返回结果执行结果：
例4 Python解决汉诺塔问题。汉诺塔(Tower of Hanoi)，又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
解：解决汉诺塔问题用递归算法编程最为简单，算法如图1所示。
图1用递归算法解汉诺塔问题示意图
# 用递归算法解汉诺塔问题
def hanoi(n, a, b, c): # 将n片圆盘从a柱上通过b柱移到c柱上
if n == 1:
print(a, '-->', c) # a柱上只有一片时直接移动到c柱
else:
hanoi(n - 1, a, c, b) # 将a柱上面n-1片圆盘通过c柱移动到b柱
print(a, '-->', c) # a柱上剩下的一张直接移至c柱
hanoi(n - 1, b, a, c) # 将b柱上n-1片圆盘通过a柱移动到c柱
n=int(input('请输入A柱上的圆盘数：'))
hanoi(n,'A','B','C')执行结果：
文章出处登录后可见！
