递归及递推基础

一 递归

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] ;
    }


感谢大家的阅读,欢迎三连

上一篇:BUUCTF 每日打卡 2021-4-11


下一篇:CMS(concurrent Mark sweep)垃圾收集器