一 递归
1 定义
递归是指将一个大问题逐渐分割成一个个小问题，直至最小可解的单元。类似于分治的思想
2 难点
在递归中，我们经常会将自己陷入到无穷多的细节中去，不断向更下层思考，增加了代码的复杂性。
3 解决
我们可以先写出代码的的第一层，然后将里面的可继续递归部分替换为递归
4 例题
写出第一层，即不需递归的形式
void out(int x)
{
int i=0;
int mark=0;
while (x/2||x==1) {
if(x%2){
a[i]=mark;
i++;
}
mark++;
x/=2;
}// 得到每一个2的幂指数
for (int j=i-1; j>=0; j--) {
if(j==0) printf("2(%d)",a[j]);
else printf("2(%d)+",a[j]);
}// 输出结果
}
}
这个时候输入9，可得
2(3)+2(0)
这个时候第一层已经成型，只需要对括号内的数字进行递归处理
void out(int x)
{
re++;
int i=0;
int mark=0;
while (x/2||x==1) {
if(x%2){
a[re][i]=mark;
i++;
}
mark++;
x/=2;
}
int temp=re;
for (int j=i-1; j>=0; j--) {
if(j==0) {
if(a[temp][j]==1) printf("2");
else {printf("2(");
if(a[temp][j]==0) printf("0");
else out(a[temp][j]);
printf(")");}
}
else{
if(a[temp][j]==1) printf("2+");
else {printf("2(");
if(a[temp][j]==0) printf("0");
else out(a[temp][j]);
printf(")+");}// 对括号内的数字进行分类处理，若是大于1，则继续递归。
}
}
}
二 递推
1 定义
递推是由想问题的方案积累，逐渐得到大问题，相比于递归，递推更有利于计算机的计算，可阅读性也更好，但是有时候不太好写
2 难点
有时候真的想不出来
3 应用
以求斐波拉切数列为例
a
[
n
]
=
a
[
n
−
1
]
+
a
[
n
−
2
]
a[n]=a[n-1]+a[n-2]
a[n]=a[n−1]+a[n−2]
int fun2(int n){
int a[] = new int[20] ;
a[1] = 1 ;
a[2] = 1 ;
for(int i=3 ; i<=n ;i++){
a[i] = a[i-1] + a[i-2] ;
}
return a[n] ;
}