尾遞歸優(yōu)化小記

Ververica 發(fā)布于2019-08-16 15:39 / 1357人閱讀

摘要：前言一般地對于語言而言普通的遞歸調(diào)用是在虛擬機(jī)棧上完成的假如是一個(gè)遞歸方法那么在其內(nèi)部再調(diào)用自己的時(shí)候假設(shè)為那么方法變量表將創(chuàng)建在方法棧幀之上從而形成了一個(gè)新的棧幀因此容易發(fā)現(xiàn)在遞歸思想中遞歸簡化了問題的表達(dá)但犧牲了虛擬機(jī)棧中的內(nèi)存空間普通

前言

一般地,對于java語言而言,普通的遞歸調(diào)用是在java虛擬機(jī)棧上完成的.假如a()是一個(gè)遞歸方法,那么在其內(nèi)部再調(diào)用自己的時(shí)候,假設(shè)為a1(),那么a1()方法變量表將創(chuàng)建在a()方法棧幀之上,從而形成了一個(gè)新的棧幀.因此容易發(fā)現(xiàn),在遞歸思想中,遞歸簡化了問題的表達(dá),但犧牲了虛擬機(jī)棧中的內(nèi)存空間.

普通遞歸 斐波那契遞歸法

public static int fib(int num){
        if(num<2)
            return num;
        else
            return fib(num-2)+fib(num-1);
    }

對于上面的解法,很容易就會發(fā)現(xiàn),不但屬于普通遞歸,而且在計(jì)算fib(num-1)是重復(fù)了fib(num-2)的計(jì)算量,因此代碼效率大打折扣.因此效率較高的寫法可以用for循環(huán)計(jì)算,

public static int fib3(int n) {
        if (n < 2)
            return n;
        else {
            int pre = 0;
            int suf = 1;
            for (int i = 2; i <= n; i++) {
                int temp = suf;
                suf += pre;
                pre = temp;
            }
            return suf;
        }
    }

斐波那契尾遞歸優(yōu)化

public class Main {
    public static void main(String[] args) {
        
        System.out.print(fib2(3, 0, 1));
    }


    public static int fib2(int count, int pre, int result) {
        if (count == 1)
            return result;
        else
            return fib2(--count, result, result + pre);
    }
}

性能對比

 public static void main(String[] args) {
        long time = new Date().getTime();

        int num=40;
        System.out.println(fib(num));
        System.out.println("普通遞歸調(diào)用用時(shí):" + (new Date().getTime() - time) + "毫秒");

        time = new Date().getTime();
        System.out.println(fib2(num, 0, 1));
        System.out.println("尾遞歸優(yōu)化調(diào)用用時(shí):" + (new Date().getTime() - time) + "毫秒");

        time = new Date().getTime();
        System.out.println(fib3(num));
        System.out.println("for循環(huán)法調(diào)用用時(shí):" + (new Date().getTime() - time) + "毫秒");
    }
    //輸出
    /*
    102334155
    普通遞歸調(diào)用用時(shí):674毫秒
    102334155
    尾遞歸優(yōu)化調(diào)用用時(shí):0毫秒
    102334155
    for循環(huán)法調(diào)用用時(shí):0毫秒
    */

可以看出有明顯差異,即使普通遞歸法計(jì)算量多了一半,時(shí)間除以2也是387毫秒,這也遠(yuǎn)遠(yuǎn)高于for循環(huán)和遞歸尾優(yōu)化法.

尾遞歸優(yōu)化思想

即遞歸方法return 直接返回方法,注意是直接返回方法,不能是方法加1個(gè)值等形式.這樣在遞歸調(diào)用時(shí),新方法會覆蓋當(dāng)前棧幀,達(dá)到節(jié)省?？臻g的目的.因此也就不會有遞歸調(diào)用產(chǎn)生的棧溢出問題.

尾遞歸寫法

斐波那契例:

//count作為計(jì)數(shù),表示遞歸層次,
//pre代表前一個(gè)值
//result 表示當(dāng)前值
 public static int fib2(int count, int pre, int result) {
        //層次減到1時(shí)返回計(jì)算結(jié)果
        if (count == 1)
            return result;
        else{
        //遞歸調(diào)用時(shí),層次減1,前一項(xiàng)更新為當(dāng)前項(xiàng),所以填result,第三個(gè)參數(shù)即實(shí)現(xiàn)了倒數(shù)第二個(gè)參數(shù)加倒數(shù)第一個(gè)參數(shù).
        return fib2(--count, result, result + pre);
        }
    }

總體而言參數(shù)的書寫分為兩部分

前部分為計(jì)數(shù),后部分為計(jì)算,例如計(jì)算階乘時(shí)候只需要兩個(gè)參數(shù),第一個(gè)計(jì)數(shù),第二個(gè)存結(jié)果.

尾遞歸將全部信息放入了參數(shù)里,因此也就巧妙地避免了需要上一棧幀保存信息.

GPU云服務(wù)器云服務(wù)器優(yōu)化遞歸數(shù)據(jù)棧尾隊(duì)列尾調(diào)用長尾詞庫

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/73619.html

發(fā)表評論

登陸后可評論

0條評論

Ververica

男|高級講師

我要關(guān)注我要私信

TA的文章

大聰明教你學(xué)Java | Hutool - A set of tools that keep Jav

閱讀 1617·2021-11-23 09:51
CSS水平垂直居中解決方案

閱讀 1185·2019-08-30 13:57
媒體查詢@media的使用

閱讀 2268·2019-08-29 13:12
Webpack HMR 原理解析

閱讀 2020·2019-08-26 13:57
用Vue搭建一個(gè)應(yīng)用盒子（二）：datetime-picker

閱讀 1205·2019-08-26 11:32
過節(jié)很無聊？還是用 JavaScript 寫一個(gè)腦力小游戲吧！

閱讀 983·2019-08-23 15:08
JavaScript運(yùn)行機(jī)制和事件循環(huán)

閱讀 710·2019-08-23 14:42
[Vue CLI 3] 插件開發(fā)之 registerCommand 到底做了什么

閱讀 3091·2019-08-23 11:41

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

尾遞歸優(yōu)化小記

斐波那契例:

相關(guān)文章