recursion
递归和递推
递归
- 从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问题。是逆向的
递推
- 从简单问题出发，一步步的向前发展，最终求得问题。是正向的。
差别
递归中问题的n 要求是计算之前就知道。而递推可以在计算中确定，不要求计算前就知道n 。
从程序上看，递归表现为自己调用自己，递推则没有这样的形式。
一般来说，递推的效率高于递归（当然是递推可以计算的情况下）
递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出
一般用递归考虑问题，然后用非递归方式编写。
例题讲解
猴子吃桃
原题链接
题目描述
猴子吃桃子问题：猴子第一天摘下若干个桃子，当即吃了一半还不过瘾，又多吃了一个；第二天又将剩下的桃子吃掉一半又多吃了一个；以后每天早上都吃了前一天剩下的一半零一个。到了第十天想再吃时，见只剩下一个桃子，求第一天共摘了多少个桃子？
输入
无
输出
一个整数，第一天共有多少个桃子。
answer
通过递归思路求得第一天为n个桃，之后每一天吃一半加一个，当第十天的时候则剩只一个，共经过9天为9次，后一天都是前一天 x/2 - 1 个，则前一天都是后一天 (x+1) * 2 个，为 2x + 2 个。
理清思路用递推来编写则为，一个变量x初始为1，经过9次计算 2x + 2 得到最终答案第一天的桃子数
1
2
3
4
5
6
7
8
9
10
11
12
| #include<iostream>
using namespace std;
int main(){
int x=1;
for(int i=1;i<10;i++){
x=x*2+2;
}
cout<<x<<endl;
}
|
过河卒
原题链接
answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<iostream>
using namespace std;
int main(){
int n,m,x,y;
cin>>n>>m>>x>>y;
// 初始化棋盘
int arr[n+1][m+1];
for (int i = 0; i < n+1; i++) {
for (int j = 0; j < m+1; j++) {
arr[i][j]=0;
}
}
// 建立马的控制点
arr[x][y]=-1;
if(y>=1 && x>=2) arr[x-2][y-1]=-1;
if(y>=1 && x<=n-2) arr[x+2][y-1]=-1;
if(y>=2 && x>=1) arr[x-1][y-2]=-1;
if(y>=2 && x<=n-1) arr[x+1][y-2]=-1;
if(y<=m-1 && x>=2) arr[x-2][y+1]=-1;
if(y<=m-1 && x<=n-2) arr[x+2][y+1]=-1;
if(y<=m-2 && x>=1) arr[x-1][y+2]=-1;
if(y<=m-2 && x<=n-1) arr[x+1][y+2]=-1;
// 递推统计每一格可达的路径数
arr[0][0]=1;
for (int i = 0; i < n+1; i++) {
for (int j = 0; j < m+1; j++) {
if(arr[i][j]==-1){
continue;
}
if(i>=1){
if(arr[i-1][j]!=-1){
arr[i][j]+=arr[i-1][j];
}
}
if(j>=1){
if(arr[i][j-1]!=-1){
arr[i][j]+=arr[i][j-1];
}
}
}
}
cout<<arr[n][m]<<endl;
}
|