问题标题: 酷町堂：在市赛前，我想学一下递推与递归

给你讲义

一、递归的定义
递归( Recursion)，是指在函数体中直接或间接调用函数自身的方法。

假设有一个函数f()，在函数体中调用本身：
f(){
     f()
}
就构成了一个递归。

二、递归的意义
一个函数本来就是用来实现某种功能，或解决某类问题的，那递归为什么要函数再调用函数自己去解决问题呢？

这是因为解决的问题规模会不一样，举个例子：
在漆黑的电影院里，每个人坐在座位上，但是不知道自己在第几排。某排（第n排）有个人想知道自己在第几排，就问他前面一排的人的排数，前面的人也不知道，于是也去问他前面的人的排数 …… 直到问到第1排，第1排的人知道自己就是第1排（前面没人了），于是他就告诉第2排的人他是1，这样第2排的人就推知自己是2，再告诉第3排的人他是2，…… 最后第n-1排的人告诉第n排的那个人自己是n-1，于是最后那个人推知自己是第n排。

三、递归的要素
【递】
即递推关系：根据某种方法，对问题进行拆分。

【归】
即终止条件：到达某种条件，问题可以直接求解，此时到达递归的边界，然后依次组合出原来大问题的解。

一、递归问题的解法
1. 如何确定递归问题
一个问题可以拆分成更细小的问题，并且拆分出的问题解结合起来就是原问题的解。拆分出的问题与原问题的本质相同，只是问题规模不同。这样的问题可以看作递归问题。

2. 递推问题的一般解法
1）确定终止条件
当问题不能继续拆分时，需要有一个最基本的解。
这保证了递归函数可终止，不会无限调用自身。

2）确定递推关系
考虑当前问题的解如何由更小规模的问题解推出来。


二、课堂题代码

递推讲义

一、递推问题的解法
1. 如何确定递推问题
在一个问题中（大多见于求方案数、种类数等问题），随着问题规模变化，结果也在变化，但是第n步变化的结果可以由前一步或前几步变化的结果推得，并且当问题规模很小时，其结果容易看出或算出，就可以考虑这个问题是递推问题。

2. 递推问题的一般解法
重难点：递推关系
假设：规模为n-1（以及更小）的问题已经有解。
分析：当问题规模扩大到n时如何求解，是否能枚举出所有可能的情况，并且每种情况都能由已有的数据推出解。
然后写出递推关系式。

重点：边界
当问题规模为1（有时甚至是0）时，结果一般能直接看出或者较容易地算出，确立此结果后，其他规模的问题都可以递推得到。

注意： 如果第n步的结果需要由之前k步的结果推出，那么就要把问题规模为1~k的结果都确定下来，作为边界。


二、课堂题代码

一、斐波那契数列
1. 问题模型
       有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子?

第一个月，只有原始的一对兔子；
第二个月，还是只有原始的一对兔子；
第三个月，原来的一对兔子生了一对小兔子，总共2对兔子
第四个月，原来的兔子又生了一对兔子，但是上个月新出生兔子还无法繁殖，总共3对兔子
第五个月，在3月出生的兔子也可以繁殖了，所以这个月增加2对兔子，总共5对兔子
第六个月，第四个月出生的兔子也可以繁殖了，所以这个月增加3对兔子，总共8对兔子
第七个月，总共出生13只兔子……
将每个月的兔子数量列出来得到一个数列：1 1 2 3 5 8 13 ……
即著名的斐波那契数列。

2. 状态及递推式
       观察斐波那契数列，我们发现除第1项、第2项外，其余各项均满足：该项的值等于前两项的值之和。
       用f[i]表示斐波那契数列第i项的数，可得递推关系：

f[i]=f[i-1]+f[i-2]
       再加上边界第1项、第2项的值：

f[1]=1;
f[2]=2;
即得到完整的斐波那契数列的递推式。

3. 斐波那契数列的特殊值
斐波那契数列第46项为1836311903，这是int能存储的下的斐波那契数列的项中的最大值。
斐波那契数列第91项为7540113804746346429，这是long long能存储的下的斐波那契数列的项中的最大值
在遇到计算斐波那契数列某项值的时候，要注意结果是否超过int范围，甚至超过long long范围。（前46项的值不超过int，前91项的值不超过long long）

4. 问题变形
       如果在开始说到的兔子繁殖问题中，兔子不是过两个月繁殖，而是每过k个月繁殖一对新的兔子，则递推关系将变为：

f[i]=f[i-1]+f[i-k]
本月的兔子数量=上月的兔子数量+k个月之前的兔子数量

数塔问题
一、问题描述

如下图是一个数塔，从顶部出发在每一个节点可以选择向左或者向右走，一直走到底层，要求找出一条路径，使得路径上的数字之和最大。
数塔问题.jpg
考虑用二维数组存储数塔
a[i][j]左下方的点为a[i+1][j],
a[i][j]右下方的点为a[i+1][j+1]。
数塔数组存储.jpg

考虑自底向上求解问题！
状态：
f[i][j]
表示从第i层第j个数字到底端能得到的最大数字之和。

边界
f[n][i]=a[n][i] (1<=i<=n)
最后一层的数字到数塔地段能得到的最大数字之和，即其本身。

目标
从第1层唯一一个数字到数塔底端能得到的最大数字之和，f[1][1].

转移方程
a[i][j]要么从左边选择一条路径要么从右边选择一条路径。
f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];

数塔问题也可以自上而下求解问题