递推典型算法：猴子爬山，跳台阶，爬楼梯(牛客网)

递推算法的基本思想是把一个复杂的、庞大的计算过程转化为简单过程的多次重复，其首要问题是得到相邻的数据项之间的关系，即递推关系。以猴子爬山为例。

1.问题的提出

一个顽猴在一座有30级太假的小山上爬山活跃，猴子上一步可跳1级或者3级，试求上山的30级台阶有多少种不同的爬法

2.简单递推设计

这一问题实际上是一个整数有序可重复拆分的问题。试应用数组递推求解，设爬k级台阶的不同爬法为f(k)种。

    上山最后一步到达第30级台阶，完成上山，共有f(30)种不同的爬法，到第30级之前位于哪一级呢？无非就是位于第29级(上跳1级即可到)，有f(29)种；或者位于第27级(上跳3级即可到)，有f(27)种；于是f(30)=f(29)+f(27)

     依次类推，有以下递推关系：

           f(k) = f(k-1)+f(k-3)            (k>3)

    f(1) = 1

    f(2) = 1

    f(3) = 2

3.递推描述