Erlang瞭解遞歸

Question

我有一些理解遞歸的問題，我希望得到一些幫助。我有兩個例子的答案，但我不明白如何計算outcomme。

f1(X, [X | Ys]) -> [X] ++ f1(X, Ys); 
f1(X, [Y| Xs]) -> tl(f1(Y, Xs)) ++ [X]; 
f1(X, []) -> [X,X]. 

如果我運行該代碼：f1（2，[1,1,1,6]）。我將得到 - > [1,6,1,2]

另一個例子：F1（C，[F，B，d，d，A]） - >並[b，F，C]

有人可以向我解釋這個函數是如何計算的嗎？ :)

，我無法掌握另一遞歸函數是這一個：

f2([X|Xs]) when X > 2 -> 
    [X|f2(XS)]; 
f2([X|Xs]) -> 
    [Y|Ys] = f2(Xs), 
    [Y,X+Y|Ys]; 
f2([]) -> [1]. 

實施例：F2（[3,1,2]）。 - > [3,1,2,3]。那個怎麼樣？

在此先感謝:)

Answer 1

這些示例使用Erlang的模式匹配。

第一實施例的第一條將匹配如果列表的第一個元素是完全一樣的第一個參數

f1(X, [X | Ys]) -> [X] ++ f1(X, Ys); 

第二子句將匹配所有的其他情況下該列表不爲空

f1(X, [Y| Xs]) -> tl(f1(Y, Xs)) ++ [X]; 

而最後一個子句匹配空列表。

f1(X, []) -> [X,X]. 

當評估f1(2, [1,1,1,6]).在第一次迭代的第二子句匹配，設定X=2，Y=1，Xs=[1,1,6]然後調用f1(1,[1,1,6])並用2所附

第二次迭代f1(1,[1,1,6])返回該搜索結果的尾巴則第一子句匹配，設置X=1,Ys=[1,6]，然後調用f1(1,[1,6])並返回該結果1前置

在第三次迭代f1(1,[1,6])也匹配第一條款，設置X=1，Ys=[6]，然後調用F1（1，[6]），並返回該結果與1前綴

的第四次迭代f1(1,[6])第二子句匹配，設定X=1 ，Y=6，Xs=[]然後調用f1(6,[])，丟棄所述第一元件，和附加1到結果

最終迭代第三子句匹配，設定X=6和返回[6,6]

放卷在棧中向上然後：

• 滴從[6,6]的第一個元素和附加1 - >返回[6,1]（第四呼叫）
• 前置1 - >返回[1 ，6,1]（第三呼叫）
• 前置1 - >返回[1,1,6,1]（第二呼叫）
• 追加2到尾 - >返回[1,6,1,2] （first call）

最終值爲[1,6,1,2]

在第二個示例中，第一個子句僅用於第一個元素。請注意，是因爲合適的列表與空List結束，模式匹配[Y|Ys] = [1]將設置Y=1和Ys=[]

編輯：添加第二個例子說明

%% If the first item in the list is greater than 2, 
%% return a new list consisting of the first item prepended 
%% to the result of recursively processing the rest of the list 
f2([X|Xs]) when X > 2 -> 
    [X|f2(XS)]; 

%% In all other cases where the list is not empty, save off 
%% the first element, then create a new list whose first 
%% element is the first element returned by the recursive call, 
%% and whose second element is the sum of that element and the 
%% first element saved above, with the rest of the recursive 
%% result appended 
f2([X|Xs]) -> 
    [Y|Ys] = f2(Xs), 
    [Y,X+Y|Ys]; 

%% return 1 if passed an empty list 
f2([]) -> [1]. 

那麼則執行以下操作：

1a. `f2([3,1,2])` matches the first clause, setting `X=3`, `Xs=[1,2]` 

    2a. `f2([1,2])` matches the second clause, setting `X=1`, `Xs=[2]` 

     3a. `f2([2])` matches the second clause, setting `X=2`, `Xs=[]` 

      4. `f2([])` matches the second clause, returning [1] 

     3b. `[Y|Ys] = [1]` sets `Y=1`, `Ys=[]` 

     3c. returns `[1, 1 + 2 | []]` i.e. `[1,3]` 

    2b. `[Y|Ys] = [1,3]` sets `Y=1`, `Ys=[3]` 

    2c. returns `[1, 1 + 1 | [3]]` i.e. `[1,2,3]` 

1b. returns `[3|[1,3,2]]` i.e. `[3,1,2,3]` 

Answer 2

除了Joe答案，您可以通過dbg模塊可視化功能執行。我把F1/2功能模塊名爲expl.erl，這裏是你可以在一個shell得到：

1> c(expl). % compile the module            
{ok,expl} 
2> dbg:tracer(). % start the dbg module          
{ok,<0.66.0>} 
3> dbg:p(all, c). % ask to trace every call          
{ok,[{matched,nonode@nohost,26}]} 
4> % show return value of calls to expl:f1/2 
4> dbg:tpl(expl, f1, 2, [{'_', [], [{return_trace}]}]). 
{ok,[{matched,nonode@nohost,1},{saved,1}]} 
5> expl:f1(2, [1,1,1,6]). % now call the function and see each call and the returned values       
[1,6,1,2] 
(<0.49.0>) call expl:f1(2,[1,1,1,6]) 
(<0.49.0>) call expl:f1(1,[1,1,6]) 
(<0.49.0>) call expl:f1(1,[1,6]) 
(<0.49.0>) call expl:f1(1,[6]) 
(<0.49.0>) call expl:f1(6,[]) 
(<0.49.0>) returned from expl:f1/2 -> [6,6] 
(<0.49.0>) returned from expl:f1/2 -> [6,1] 
(<0.49.0>) returned from expl:f1/2 -> [1,6,1] 
(<0.49.0>) returned from expl:f1/2 -> [1,1,6,1] 
(<0.49.0>) returned from expl:f1/2 -> [1,6,1,2] 
6> dbg:stop_clear(). % stop dbg and clear trace         
ok 
7>