递推

递推算法基本思想

递推算法是一种理性思维莫斯的代表，根据已有的数据和关系，逐步推到而得到结果。递推算法的执行过程如下：

（1）根据已知结果和关系，求解中间结果。

（2）判断是否达到要求，如果没有达到，则继续根据已知结果和关系求解中间结果。如果满足要求，则表示寻找到一个正确答案。

递推算法的关键在于，每一项都和他前面的若干项由一定的关联，这种关联一般可以通过递推关系式来表示。递推式第x项通常用f(x)表示。例如：第一项是1，第二项是2。那么f(1)=1,f(2)=2。

例题

已知一对兔子，每个月可以生一对小兔子，小兔子出生后的第二个月会变成年兔子，会继续生小兔子。

第一个月，我们有 1 对小兔子。
第二个月，我们有 1 对成年的兔子。
第三个月，我们有 1 对成年的兔子，有 1 对小兔子，共 2 对。
第四个月，我们有 2 对成年的兔子，有 1 对小兔子，共 3 对。
第五个月，我们有 3 对成年的兔子，有 2 对小兔子，共 5 对。
.....

请问n月后，有多少只兔子？

分析：前五个月分别为：f(1)=1,f(2)=1,f(3)=2,f(4)=3,f(5)=5。从第三项开始，观察每一项与前面的关系。可发现，f(3)=f(2)+f(1)，f(4)=f(3)+f(2)。也就是说，每一项等于他前两项之和。由此可列出出通项公式，f(n)=f(n-1)+f(n-2)。也就是所谓的“根据已知结果和关系，求解中间结果”。这就是著名的“斐布拉切数列”代码如下。

#include<bits/stdc++.h>
using namespace std;
int n,f[10005]; //f数组表示第i个月有几只兔子。 
int main()
{
	cin>>n;
	f[1]=1,f[2]=1;
	for(int i=3;i<=n;i++) f[i]=f[i-1]+f[i-2]; //带入通向公式，根据已知结果和关系，求解中间结果。 直到第n个月。 
	cout<<f[n]; //如果满足要求，则表示寻找到一个正确答案 
	return 0;
}

递推算法有着敏锐的数感。碰到繁琐的式子时不要着急，通过已知项找通项公式并求解。最后推荐几道题。

双塔问题

数的划分

参考资料：https://blog.csdn.net/Richard__Ting/article/details/79679648