一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。
无论顺推还是逆推，其关键是要找到递推式
顺推法
所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。
逆推法
所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。
递归算法三：汉诺塔
问题描述
移动规则：
每次只能移动一个圆盘；
圆盘可以插在A、 B和C中的任何一个塔座上；
任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
分析
边界条件
只有一个圆环时，只需将圆环从第一座塔移到第三座塔
递归条件
1、从第一座塔把n-1个圆环移到第二座塔，用第三座塔做辅助
2、从第一座塔把第n个圆环移到第三座塔
3、从第二座塔把n-1个圆环移到第三座塔，用第一座塔做辅助
代码
简单汉诺塔递归实现
#include<iostream>
using namespace std;
void move(char from, char to){
cout<<"Move"<<from<<"to"<<to<<endl;
}
void hanoi(int n, char first, char second, char third){
if(n==1){
move(first, third);
}else{
hanoi(n-1, first, third, second);
move(first, third);
hanoi(n-1, second, first, third);
}
}
int main(){
int m;
cout<<"the number of diskes:";
cin>>m;
cout<<"move "<<m<<" diskes:
";
hanoi(m,'A','B','C');
return 0;
}
汉诺塔递推实现
#include<iostream>
using namespace std;
int main(){
int m;
cin>>m;
long long p = 0;
for(int i=0; i<m; i ){
p=2*p 1;
}
cout<<2*p<<endl;
return 0;
}