前面有討論過遞迴,今天來討論尾遞迴.

把前面的mylen

-module(mylen).
-export([len/1]).

len([]) -> 0;
len([_|T]) -> 1 + len(T).

另外使用尾遞迴方式

-module(mytaillen).
-export([taillen/1]).

taillen(List) -> len_acc(List, 0).

len_acc([], N) -> N;
len_acc([_ | Tail], N) -> len_acc(Tail, N + 1).

來看執行過程,先看 空List [] 的情況.

taillen([]) -> len_acc([], 0).
然後
lan_acc([], N) -> N;
會符合模式比對,這時候 0 會傳遞給N.
最終得到解答,傳回0.
這時候已經先確定,當空List時,此函數能有效運作.
接著來看傳 [1,2,3] 進去時的情況.

taillen([1,2,3]) -> len_acc([1,2,3], 0).
然後len_acc 的第2項 len_acc([_ | Tail], N) 符合模式.
餘此類推.
現在把計算過程列在下面.用 => 代表過程.注意,這不是erlang的符號,
這是為了行文解釋方便引用的.

taillen([1,2,3])
 => len_acc([1,2,3], 0)
 => len_acc([2,3], 1)
 => len_acc([3], 2)
 => len_acc([], 3)
 => 3

最終符合 len([], N), 得到解答 3.

再來看 sum,前面介紹遞迴時,也有一個sum,如下:

-module(mysum).
-export([sum/1]).

sum([H | T]) -> H + sum(T);
sum([]) -> 0.

這很直觀.接著我們來看如何改用尾遞迴方式.

-module(tailsum).
-export([tailsum/1]).

tailsum(List) -> sum_acc(List, 0).

sum_acc([], Sum) -> Sum;
sum_acc([Head | Tail], Sum)
  -> sum_acc(Tail, Head + Sum).

推導過程:

tailsum([1,2,3])
  => sum_acc([1,2,3], 0) 這裡的零會傳遞給Sum,就好像一般寫 Sum = 0
  => sum_acc([2,3], 1)
  => sum_acc([3], 3)
  => sum_acc([], 6)
  => 6

最終得解.

看了這些遞迴與尾遞迴的例子,大家心裡也許有疑問?
既然前面有強調erlang的變數不能改變,那為何這裡的Sum,
卻一直改變呢?
這裡要說明一下,erlang寫的式子,變數是不能改變,
但是再呼叫時,每次都是重新評估,式子是一樣的,
但是執行時,是單獨的,上面的式子中,
雖然可以看到 sum_acc 裡的Sum,好似一直變化,
實際上並不同.
要先有這觀念,接著我們來討論為何要用尾遞迴??

一般程式語言也有遞迴,但是用的少.有兩個主要原因,
一個是程式語法造成理解與撰寫相對較難,
另一個是效能因素,因為使用遞迴需要一直呼叫函數,
這時候CPU必須將函數在記憶體裡的位址,放到堆疊區段,
就好像我們登山或走迷宮,會一路留下記號,
直到求解時,一路返回.這時候CPU不斷進行跳躍,
效能相對低落,而且有堆疊區段可能爆滿的問題.

在erlang則不同,早期版本的erlang使用尾遞迴的技巧,
compile時,可以變成loop形式,從而大量提高效率與
有效使用記憶體,這是一個重大突破;也是erlang高效的
一個原因.
但是在目前較新版的erlang,不管是使用原本遞迴的方式,
或是尾遞迴的方式,根據今(2014)年9月的文件,經過優化
之後,目前兩者速度幾乎是一樣的;而且有些情境下,
最後需要呼叫 lists:reverse(),來將list反轉.
所以不見得使用尾遞迴會較快!

依據CPU架構的不同, Solaris/Sparc,兩者幾乎等速;
x86架構,尾遞迴快大約30%.

如上面所探討的,目前無須硬要用尾遞迴,我們可以視自己
思維推導順利寫出,運作良好即可.有些狀況下,
尾遞迴比較好推導出來.但也不見得整體效率就一定高.
先交給erlang來幫我們優化!