递推算法
递推算法
递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。递推算法分为顺推和逆推两种。
详情请到百度百科> https://baike.baidu.com/item/%E9%80%92%E6%8E%A8%E7%AE%97%E6%B3%95/2025952?fr=aladdin
典型例题：Fibonacci(斐波那契数列)
{1 1 2 3 5 8 13 21 34........}
求数列第n项。
不难发现，从第三项开始，每一项都等于它的上一项和上上一项。
满足Fn=Fn-1+Fn-2.
利用这一规律，代码如下。
#include<iostream> using namespace std; int main() { int n,f1=1,f2=1,f3; cin>>n; for(int i=3;i<=n;i++) { f3=f1+f2; f1=f2; f2=f3; } cout<<f3; return 0; }
原理很容易理解，这里就不啰嗦了，直接看一道例题。
题目描述
楼梯有 N 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入格式
一个数字，楼梯数。
输出格式
输出走的方式总数。
输入输出样例
输入 #14
输出 #15
这道题看似与上面没有一点关系，但仔细想想会发现
假设总共10级台阶，我们倒着推，最后一步要么上1，要么上2；上1的话，就取决于上F9，上2的话，取决于F8。
因此得出Fn=Fn-1+Fn-2.
这恰好就是斐波那契数列。