Erlang遞歸
遞歸是 Erlang 的重要組成部分。首先,讓我們通過實現階乘程序來了解簡單的遞歸。
示例
-module(helloworld).
-export([fac/1,start/0]).
fac(N) when N == 0 -> 1;
fac(N) when N > 0 -> N*fac(N-1).
start() ->
X = fac(4),
io:fwrite("~w",[X]).
對於上面的例子,有以下幾點需要注意 -
我們首先定義一個函數 fac(N);
我們可以通過定義遞歸函數 fac(N) 遞歸;
上面的代碼的輸出結果是 -
24
實用方法遞歸
在本節中,我們將詳細瞭解不同類型的遞歸及其在 Erlang 中的使用。
長度遞歸
以遞歸一個更有效的方法可以用於確定一個列表的長度,現在來看看一個簡單的例子。列表中有多個值,如[1,2,3,4]。
讓我們用遞歸的方法來看看如何能夠得到一個列表的長度。
示例
-module(helloworld).
-export([len/1,start/0]).
len([]) -> 0;
len([_|T]) -> 1 + len(T).
start() ->
X = [1,2,3,4],
Y = len(X),
io:fwrite("~w",[Y]).
以下是上述程序需要說明的一些關鍵點 -
第一個函數 len([]) 用於特殊情況的條件:如果列表爲空。
[H|T] 模式來匹配一個或多個元素的列表,如長度爲1的列表將被定義爲 [X|[]],而長度爲 2 的列表將被定義爲 [X|[Y|[]]] 。
注意,第二元素是列表本身。這意味着我們只需要計數第一個,函數可以調用它本身在第二元素上。在列表給定每個值的長度計數爲 1 。
上面的代碼的輸出結果是 -
4
尾部遞歸
要了解尾遞歸是如何工作的,讓我們來了解下面的代碼在上一節中是如何工作的。
語法
len([]) -> 0;
len([_|T]) -> 1 + len(T).
回答 1 + len(Rest) 需要 len(Rest) 。函數 len(Rest) 根據需要自行調用另一個函數的結果。該補充將得到堆積,直到最後一個被發現,然後纔會計算最終結果。尾遞歸旨在通過減少它們,以消除這種操作堆疊。
爲了達到這個目的,我們將需要保持一個額外的臨時變量作爲函數的一個參數。上述臨時變量有時被稱爲累加器並用來存儲計算的結果,因爲它們會限制調用增長。
讓我們來看看尾遞歸的一個例子 -
示例
-module(helloworld).
-export([tail_len/1,tail_len/2,start/0]).
tail_len(L) -> tail_len(L,0).
tail_len([], Acc) -> Acc;
tail_len([_|T], Acc) -> tail_len(T,Acc+1).
start() ->
X = [1,2,3,4],
Y = tail_len(X),
io:fwrite("~w",[Y]).
上面的代碼的輸出結果是 -
4
重複(複本)
讓我們來看看遞歸的例子。這一次我們寫一個函數,它接受一個整數作爲其第一個參數,然後有一個其他子句作爲其第二個參數。它將由整數指定創建多個副本的列表。
讓我們來看看這個例子如下 -
-module(helloworld).
-export([duplicate/2,start/0]).
duplicate(0,_) ->
[];
duplicate(N,Term) when N > 0 ->
io:fwrite("w,n",[Term]),
[Term|duplicate(N-1,Term)].
start() ->
duplicate(5,1).
上面的代碼的輸出結果是 -
1,
1,
1,
1,
1,
列表反轉
有無止境的在 Erlang 中使用遞歸。讓我們現在快速地來看看如何使用遞歸來反轉列表的元素。
下面的程序可用於實現此目的。
示例
-module(helloworld).
-export([tail_reverse/2,start/0]).
tail_reverse(L) -> tail_reverse(L,[]).
tail_reverse([],Acc) -> Acc;
tail_reverse([H|T],Acc) -> tail_reverse(T, [H|Acc]).
start() ->
X = [1,2,3,4],
Y = tail_reverse(X),
io:fwrite("~w",[Y]).
上面的代碼的輸出結果是 -
[4,3,2,1]
以下是上述程序需要說明的一些關鍵點 -
我們再次使用臨時變量 Acc 存儲列表中的每個元素
調用遞歸尾反轉,確保最後一個元素被放入新列表的第一位置
遞歸調用尾反向列表中的每個元素