沐鳴平台網站_尾調用與尾遞歸

本講將對尾調用與尾遞歸進行介紹:函數的最後一條執行語句是調用一個函數的形式即為尾調用;函數尾調用自身則為尾遞歸,通過改寫循環即可輕鬆寫出尾遞歸函數。在語言支持尾調用優化的條件下,尾調用能節省很大一部分內存空間。

什麼是尾調用

問:何為尾調用?

說人話:函數的最後一條執行語句是調用一個函數,這種形式就稱為尾調用。

讓我們看看以下幾個例子。

// 正確的尾調用:函數/方法的最後一行是去調用function2()這個函數
public int function1(){
    return function2();
}

// 錯誤例子1:調用完函數/方法后,又多了賦值操作
public int function1(){
    int x = function2();
    return x;
}

// 錯誤例子2:調用完函數后,又多了運算操作
public int function1(){
    return function2() + 1;
}

// 錯誤例子3:f(x)的最後一個動作其實是return null
public void function1(){
    function2();
}

尾調用優化

以Java為例。JVM會為每個新創建的線程都創建一個棧(stack)。棧是用來存儲棧幀(stack frame)的容器;而棧幀是用來保存線程狀態的容器,其主要包括方法的局部變量表(local variable table),操作數棧(operand stack),動態連接(dynamic linking)和方法返回地址(return address)等信息。

(注:Java語言目前還不支持尾調用優化,但尾調用優化的原理是相通的。)

棧會對棧幀進行壓棧和出棧操作:每當一個Java方法被執行時都會新創建一個棧幀(壓棧,push),方法調用結束后即被銷毀(出棧,pop)。

在方法A的內部調用方法B,就會在A的棧幀上疊加一個B的棧幀。在一個活動的線程中,只有在棧頂的棧幀才是有效的,它被稱為當前棧幀(Current Stack Frame),這個棧幀所關聯的方法則被稱為當前方法(Current Method)。只有當方法B運行結束,將結果返回到A后,B的棧幀才會出棧。

舉個例子。

public int eat(){
    return 5;
}

public int action(){
    int x = eat();
    return x;
}

public int imitate(){
    int x = action();
    return x;
}

public static void main(String[] args){
    imitate();
}

這段代碼對應的棧的狀況則為如下:

首先,在main線程調用了 imitate() 方法,便將它的棧幀壓入棧中。

在 imitate() 方法里,調用了 action() 方法,由於這不是個尾調用,在調用完 action() 方法后仍存在一個運算操作,因此將 action a c t i o n  的棧幀壓入棧中后,JVM認為 imitate() 方法還沒執行完,便仍然保留着 imitate i m i t a t e  的棧幀。

同理: action() 方法里對 eat() 方法的調用也不是尾調用,JVM認為在調用完 eat() 方法后, action() 方法仍未執行結束。因此保留 action a c t i o n  的棧幀,並繼續往棧中壓入 eat e a t  的棧幀。

eat() 方法執行完后,其對應棧幀就會出棧; action() 方法和 imitate() 方法在執行完后其對應的棧幀也依次出棧。

但假如我們對上述示例代碼改寫成如下所示:

public int eat(){
    return 5;
}

public int action(){
    return eat();
}

public int imitate(){
    return action();
}

public static void main(String[] args){
    imitate();
}

那麼如果尾調用優化生效,棧對應的狀態就會為如下:

首先,仍然是將 imitate() 方法的棧幀壓入棧中。

在 imitate() 方法中對 action() 方法進行了尾調用,因此在調用 action() 方法時就意味着 imitate() 方法執行結束: imitate i m i t a t e  棧幀出棧, action a c t i o n  棧幀入棧。

同理: action a c t i o n  棧幀出棧, eat e a t  棧幀入棧。

最後, eat() 方法執行完畢,全流程結束。

我們可以看到,由於尾調用是函數的最後一條執行語句,無需再保留外層函數的棧幀來存儲它的局部變量以及調用前地址等信息,所以棧從始至終就只保留着一個棧幀。這就是 尾調用優化(tail call optimization) ,節省了很大一部分的內存空間。

但上面只是理論上的理想情況,把代碼改寫成尾調用的形式只是一個前提條件,棧是否真的如我們所願從始至終只保留着一個棧楨還得取決於語言是否支持。例如python就不支持,即使寫成了尾遞歸的形式,棧該爆還是會爆。

尾遞歸

問:何為尾遞歸?

說人話:函數尾調用自身,這個形式就稱為尾遞歸。

在手把手教你寫遞歸這篇文章中我們提過,遞歸對空間的消耗大,例如計算 factorial(1000) ,就需要保存1000個棧幀,很容易就導致棧溢出。

但假如我們將其改為尾遞歸,那對於那些支持尾調用優化的語言來說,就能做到只保存1個棧幀,有效避免了棧溢出。

那尾遞歸函數要怎麼寫呢?

一個比較實用的方法就是先寫出用循環實現的版本,再把循環中用到的局部變量都改為函數的參數即可。這樣再進入下一層函數時就不需要再用到上一層函數的環境了,到最後一層時就包含了前面所有層的計算結果,就不要再返回了。

例如階乘函數。

public int fac(int n) {
    int result = 1;
    for (int index = 1; index <= n; index++)
        result = index * result;
    return result;
}

在這個用循環實現的版本中,可以看到用到了 result,index r e s u l t , i n d e x  這兩個局部變量,那就將其改為函數的參數。並且通過循環可以看出邊界條件是當 index == n 時; n n  從頭到尾不會變; index i n d e x  在每次進入下一層循環時會遞增, result r e s u l t  在每次進入下一層循環時會有變動。我們把這些改動直接照搬,改寫就非常容易了。

所以用尾遞歸實現的版本即為如下:

public int fac(int n, int index, int result) {
    if (index == n)
        return index * result;
    else 
        return fac(n, index + 1, index * result);
}

再舉個例子,斐波那契數列(0, 1, 1, 2, 3, 5, 8, 13…)

其循環實現版本如下:

public int fibo(int n) {
    int a = 0;
    int b = 1;
    int x = 0;
    for (int index = 0; index < n; index++){
    	x = b;
        b = a + b;
        a = x;
    }
    return a;
}

局部變量有 a,b,index a , b , i n d e x  ( x x  作為 a,b a , b  賦值的中間變量,在遞歸中可以不需要用到),把這些局部變量放到參數列表。邊界條件為當 index == n 時;並且,在進入下一層循環時, a a  的值會變為 b b  , b b  的值會變為 a+b a + b  , index i n d e x  的值加1,把這些改動照搬。

public int fibo(int n, int a, int b, int index) {
    if (index == n) 
        return a;
    else 
        return fibo(n, b, a + b, index + 1);
}

原文 http://www.cnblogs.com/linj7/p/14163265.html

站長推薦

1.雲服務推薦: 國內主流雲服務商,各類雲產品的最新活動,優惠券領取。地址:阿里雲騰訊雲華為雲

2.廣告聯盟: 整理了目前主流的廣告聯盟平台,如果你有流量,可以作為參考選擇適合你的平台點擊進入

鏈接: http://www.fly63.com/article/detial/9955