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]模式與一個或多個元素的列表匹配，長度為一的列表將定義為[X|[]]，長度為二的列表將定義為[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的變數中。

• 然後我們遞迴呼叫tail_reverse，但是這次我們確保最後一個元素首先放入新列表中。

• 然後我們遞迴地為列表中的每個元素呼叫tail_reverse。