数据结构与算法-递归

1.什么是递归

 举一个例子:大学军训的时刻,一个队伍,开头的人A想知道这个队伍一共有多少人,然则每小我私家只能通过旁边的交流,那若何统计呢?

    我们可以先找出最后一小我私家,A可以问旁边的人B是否为最后一小我私家,B又问下一小我私家,云云类推,等到了最后一小我私家,再将号码返回到第一小我私家A,每往前一个,号码上就+1,第一小我私家A就知道这个队伍有多少人了。

    公式:g(n)=g(n-1)+1;g(1)=1

数据结构与算法-递归

int AskNumberOfTeams(int n) {
    if(n == 1) {
        return 1;
    }
    return 1 + AskNumberOfTeams(n-1);
}

  递归可以看成一个嵌套的形式,一层层嵌套,执行相同的内容,到终止条件后往上返回效果。

数据结构与算法-递归

  递归有三个要素:1.判断问题能否才分成小问题;2.每个小问题解决方案是否一致;3.是否有终止条件

2.简朴应用

opentsdb探索之路——部分设计与实现

  斐波拉契数列

    斐波拉契数列指的是1、1、2、3、5、8、13、21、34、55……。我们凭据数列可以推导出,当前n位置的数值可以早年两个数值和获得,公式为f(n)=f(n-1)+f(n-2),f(1)=1与f(2)=1这两个是递归的终止条件。  

int CalFibonacci(int n) {
    if(n == 1 || n == 2) {
        return 1;
    }
    return CalFibonacci(n-1) + CalFibonacci(n - 2);
}

   阶乘

         阶乘n!是小于即是n的正整数的积,而且0!=1,n!=1*2*3*4*……*(n-2)*(n-1)*n。凭据公式可以拆分成n!=(n-1)!*n,且终止条件为0!=1。

int CalFactorial(int n) {
    if(n == 0) {
        return 1;
    }
    return CalFactorial(n - 1) * n;
}

3.递归写成非递归的形式

    递归的形式都是可以写成非递归的形式,用循环来替换递归。以上上面两个应用可以改写成:

    斐波拉契数列

int CalFibonacciCycle(int n) {
    if(n == 1 || n == 2) {
        return 1;
    }
    int SecondValue = 1;//f(n-2)
    int FirstValue = 1;//f(n-1)
    int resultvalue;//f(n)
    for(int i=3; i<=n; i++) {
        resultvalue = FirstValue + SecondValue;
        SecondValue = FirstValue;
        FirstValue = resultvalue;
    }
    return resultvalue;
}

  阶乘

int CalFactorialCycle(int n) {
    if(n == 0) {
        return 1;
    }
    int FirstValue = 1;//f(n-1)
    int resultvalue;//f(n)
    for(int i=1; i<=n; i++) {
        resultvalue = i * FirstValue;
        FirstValue = resultvalue;
    }
    return resultvalue;
}

 

原创文章,作者:28x29新闻网,如若转载,请注明出处:https://www.28x29.com/archives/4291.html