尾遞歸優化小記

張率功發布于2019-07-31 10:08 / 1168人閱讀

摘要：前言一般地對于語言而言普通的遞歸調用是在虛擬機棧上完成的假如是一個遞歸方法那么在其內部再調用自己的時候假設為那么方法變量表將創建在方法棧幀之上從而形成了一個新的棧幀因此容易發現在遞歸思想中遞歸簡化了問題的表達但犧牲了虛擬機棧中的內存空間普通

前言

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

普通遞歸 斐波那契遞歸法

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

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

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

斐波那契尾遞歸優化

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("普通遞歸調用用時:" + (new Date().getTime() - time) + "毫秒");

        time = new Date().getTime();
        System.out.println(fib2(num, 0, 1));
        System.out.println("尾遞歸優化調用用時:" + (new Date().getTime() - time) + "毫秒");

        time = new Date().getTime();
        System.out.println(fib3(num));
        System.out.println("for循環法調用用時:" + (new Date().getTime() - time) + "毫秒");
    }
    //輸出
    /*
    102334155
    普通遞歸調用用時:674毫秒
    102334155
    尾遞歸優化調用用時:0毫秒
    102334155
    for循環法調用用時:0毫秒
    */

可以看出有明顯差異,即使普通遞歸法計算量多了一半,時間除以2也是387毫秒,這也遠遠高于for循環和遞歸尾優化法.

尾遞歸優化思想

即遞歸方法return 直接返回方法,注意是直接返回方法,不能是方法加1個值等形式.這樣在遞歸調用時,新方法會覆蓋當前棧幀,達到節省棧空間的目的.因此也就不會有遞歸調用產生的棧溢出問題.

尾遞歸寫法

斐波那契例:

//count作為計數,表示遞歸層次,
//pre代表前一個值
//result 表示當前值
 public static int fib2(int count, int pre, int result) {
        //層次減到1時返回計算結果
        if (count == 1)
            return result;
        else{
        //遞歸調用時,層次減1,前一項更新為當前項,所以填result,第三個參數即實現了倒數第二個參數加倒數第一個參數.
        return fib2(--count, result, result + pre);
        }
    }

總體而言參數的書寫分為兩部分

前部分為計數,后部分為計算,例如計算階乘時候只需要兩個參數,第一個計數,第二個存結果.

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

GPU云服務器云服務器優化遞歸數據棧尾隊列尾調用長尾詞庫

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43320.html

尾遞歸優化小記

摘要：前言一般地對于語言而言普通的遞歸調用是在虛擬機棧上完成的假如是一個遞歸方法那么在其內部再調用自己的時候假設為那么方法變量表將創建在方法棧幀之上從而形成了一個新的棧幀因此容易發現在遞歸思想中遞歸簡化了問題的表達但犧牲了虛擬機棧中的內存空間普通前言一般地,對于java語言而言,普通的遞歸調用是在java虛擬機棧上完成的.假如a()是一個遞歸方法,那么在其內部再調用自己的時候,假設為a1...

Ververica 2019-08-16 15:39 評論0 收藏0
尾遞歸優化小記

摘要：前言一般地對于語言而言普通的遞歸調用是在虛擬機棧上完成的假如是一個遞歸方法那么在其內部再調用自己的時候假設為那么方法變量表將創建在方法棧幀之上從而形成了一個新的棧幀因此容易發現在遞歸思想中遞歸簡化了問題的表達但犧牲了虛擬機棧中的內存空間普通前言一般地,對于java語言而言,普通的遞歸調用是在java虛擬機棧上完成的.假如a()是一個遞歸方法,那么在其內部再調用自己的時候,假設為a1...

Drinkey 2019-08-26 13:34 評論0 收藏0
Python開啟尾遞歸優化!

摘要：尾遞歸優化一般遞歸與尾遞歸一般遞歸執行可以看到一般遞歸每一級遞歸都產生了新的局部變量必須創建新的調用棧隨著遞歸深度的增加創建的棧越來越多造成爆棧尾遞歸尾遞歸基于函數的尾調用每一級調用直接返回遞歸函數更新調用棧沒有新局部變量的產生類似迭代的 Python尾遞歸優化一般遞歸與尾遞歸一般遞歸: def normal_recursion(n): if n == 1: ...

junnplus 2019-07-31 10:54 評論0 收藏0
尾調用和尾遞歸

摘要：執行完了，銷毀調用棧中自己的記錄，依次銷毀和的調用幀，最后完成整個流程。尾遞歸定義先來看一下遞歸，當一個函數調用自身，就叫做遞歸。尾調用 1. 定義尾調用是函數式編程中一個很重要的概念，當一個函數執行時的最后一個步驟是返回另一個函數的調用，這就叫做尾調用。注意這里函數的調用方式是無所謂的，以下方式均可：函數調用: func(···) 方法調用: obj.meth...

goji 2019-08-22 16:09 評論0 收藏0
js 實現斐波那契數列(數組緩存、動態規劃、尾調用優化)

摘要：根據該規則，返回第個斐波那契數。尾遞歸函數調用自身，稱為遞歸。一個前端眼中的斐波那契數列解斐波那契數列的實用解法調用棧尾遞歸和手動優化尾調用優化譯我從用寫斐波那契生成器中學到的令人驚訝的件事斐波那契數列是以下一系列數字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數字 0 和 1 ...

趙連江 2019-08-23 11:38 評論0 收藏0