算法总结之递推与递归
递推算法
递归算法⼤致包括两⽅⾯的内容：1）递归起点 ； 2）递归关系
递推起点
递归起点⼀般由题⽬或者实际情况确定，不由递归关系推出。如果⽆法确定递归起点，那么递归算法就⽆法实现。可见，递归起点是递归算
法中的重要⼀笔。
递推关系递归关系是递归算法的核⼼。常见的递归关系有以下⼏项：
1）⼀阶递推；
2）多阶递推；
3）间接递推；
4）逆向递推；
5）多维递推。
下⾯通过栗⼦来详细介绍⼀下上述类别的递推关系。
1. ⼀阶递推
在计算f(i)时，只⽤到前⾯项中的⼀项，如等差数列。公差为3的等差数列，其递推关系为：
f(i)=f(i-1)+3
eg. 平⾯上10条直线最多能把平⾯分成⼏部分？
分析：以直线数⽬为递推变量，假定i条直线把平⾯最多分成f(i)部分，则f(i-1)表⽰i-1条直线把平⾯分成的最多部分。在i-1条直线的平⾯上增
加直线i，易得i与平⾯上已经存在了的i-1条直线最多各有⼀个交点，即直线i最多被分成i段，⽽这i段将会依次将平⾯⼀分为⼆，即直线i将最
多使平⾯多增加i部分。所以，递推关系可表⽰为：f(i)=f(i-1)+i
易得当0条直线时，平⾯为1部分。所以f(0)=1为递推起点。
上述分析可⽤下⾯代码表⽰（c++）：
#define MAX 100
int f[MAX] //存放f（i）
int lines(int n){
//输⼊n为直线数⽬
//输出最多部分数
int i;
f(0)=1;
for(i=1;i<=n;i++){
f[i]=f[i-1]+3;
}
return f[i];
}
2. 多阶递推
在计算f(i)时，要⽤到前⾯计算过的多项，如Fibonacci数列。
eg.求Fibonacci的第10项。
分析：总所周知，Fibonacci数列中的第n项等于第n-1项加上n-2项。所以递推关系为
f(i)=f(i-1)+f(i-2);且f[0]=f[1]=1。
C++代码如下：
#define MAX 100
稳定的递推算法
1 稳定的递推算法是什么？
稳定的递推算法是指一种通过已知的初始值和递推公式计算后续值的数学算法。这种算法不仅能够正确和快速地计算出数列中每一项的值，而且其计算过程是稳定可靠的，不会出现数据不准确或计算错误的情况。
2 递推算法的基本原理
递推算法是一种基于数学归纳法的算法。具体地说，其基本原理是依据已知的初值和递推关系式，逐步推导出数列中的每一项的值。递推算法的一般形式为：
f(n) = g(f(n-1))
其中，f(n) 是数列中第 n 项的值，g 是递推关系式，f(n-1) 是数列中的前一项。
3 稳定递推算法的特点
稳定递推算法有以下特点：
1. 不会出现“死循环”：这是因为递推公式和初值的限制条件能够确保计算过程的唯一性和有限性。
2. 对于相同的初值和递推公式，计算结果的可复现性非常好，而且速度较快。 3. 稳定递推算法的计算量较小，适用于大型数列的计算。
4 稳定递推算法在计算机科学中的应用
稳定递推算法在计算机科学中有着广泛的应用，特别是在数据结构和算法领域。下面介绍其中两个经典的例子：
1. 斐波那契数列
斐波那契数列是指这样一个数列：0、1、1、2、3、5、8、13、21、34、… 其中每一项都是前两项的和。这个数列可以使用递推算法进行计算，而且计算速度很快。
2. 动态规划算法
动态规划算法是一种递推算法，其应用广泛，涵盖了很多领域，比如图像处理、自然语言处理、人工智能等。动态规划算法通常是在递归的基础上进行计算，但是由于递推公式的稳定性，其速度通常会比递归算法快得多。
5 稳定递推算法的实现方式
稳定递推算法的实现方式通常是使用循环结构，在每一次循环中，根据递推公式和前一项的值计算出当前项的值，并赋值给当前项。循环的次数就是要求的数列的项数。
6 稳定递推算法的优化
稳定递推算法的优化主要是通过改善递推公式和优化循环结构来提高算法的效率和稳定性。一些文献指出，使用矩阵乘法等方法可在一定程度上提高递推算法的计算速度。 7 稳定递推算法的应用场景
第二讲递推算法
部门： xxx
时间： xxx
整理范文，仅供参考，可下载自行编辑第二讲递推算法
一、引例：Fibonacci数列
Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”>。b5E2RGbCAP
• 问题：一个数列的第0项为0，第1项为1，以后每一项都是前两项的和，这个数列就是著名的裴波那契数列，求裴波那契数列的第N项。 p1EanqFDPw
解答：
• 由问题,可写出递推方程
算法：
F[0] := 1。 F[1] := 2。
FOR i := 2 TO N DO
F[I] := F[I – 1] + F[I – 2]。
总结：从这个问题可以看出，在计算裴波那契数列的每一项时，都可以由前两项推出。这样，相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关系式：Fn=g(Fn-1>，这就在数的序列中，建立起后项和前项之间的关系。然后从初始条件
二、递推概念：
给定一个数的序列H0,H1,…,Hn,…若存在整数n0，使当n>n0时,可以用等号(或大于号、小于号>将Hn与其前面的某些项Hn(0联系起来，这样的式子就叫做递推关系。5PCzVD7HxA
– 如何建立递推关系
– 递推关系有何性质
– 如何求解递推关系
递推的形式
• 顺推法和倒推法
三、应用举例
例1：昆虫繁殖
科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵>，问过Z个月以后，共有成虫多少对？x>=1,y>=1,z>=x
输入：x,y,z的数值
输出：成虫对数
示例：
输入：x=1 y=2 z=8
输出：37
分析 ：
首先我们来看样例：每隔1个月产2对卵，求过8月
几种最小二乘法递推算法的小结
最小二乘法是一种常见的参数估计方法，广泛应用于各个领域的数学和统计模型的拟合问题。在实际应用中，我们常常需要递推地计算最小二乘法的结果，以便能够在实时数据到来的情况下，快速地更新参数估计值。以下是几种常见的最小二乘法递推算法的小结。
1. 递推最小二乘法（Recursive least squares, RLS）
递推最小二乘法是一种在线参数估计方法，可以在每次新数据到来时，快速地更新参数估计值。RLS算法利用递推的方式，将历史数据和新数据的信息结合起来，从而得到最新的参数估计值。该算法基于递归迭代过程，迭代公式中的权重矩阵可以由历史数据的协方差矩阵递推得到。递推最小二乘法具有良好的收敛性和较低的计算复杂度。
2.递推最小二乘法的变种算法（RLS的变种算法）
递推最小二乘法的变种算法是对传统的RLS算法进行改进和优化的方法。其中，经典的改进算法有递归正交最小二乘法（Recursive
orthogonal least squares, ROLS）和递推快速QR分解法（Recursive
fast QR factorization, RFQR）。ROLS算法通过引入正交化处理，解决了经典RLS算法中信号相关性较高时，参数估计不稳定的问题。RFQR算法则通过对历史数据进行快速QR分解的方法，进一步提高了算法的计算速度，并降低了计算复杂度。
3. 渐进最小二乘法（Asymptotic least squares, ALS）
渐进最小二乘法是一种常见的在线参数估计算法，用于解决参数估计问题的收敛速度较慢的情况。ALS算法通过估计参数的渐进协方差矩阵，然后利用资料增益矩阵计算最新的参数估计值。由于ALS算法不需要存储和计算全部历史数据的相关矩阵，因此可以在实时数据到来的情况下，快速地进行参数估计。
4. 数据辅助递推最小二乘法（Data-augmented recursive least
