Erlang 理解递归

Question

我在理解递归时遇到一些问题，希望得到一些帮助。我有 2 个示例和答案，但我不明白结果是如何计算的。

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])，并用[=返回结果25=] 前置

第四次迭代f1(1,[6])匹配第二个子句，设置X=1、Y=6、Xs=[]然后调用f1(6,[])，丢弃第一个元素，然后将 1 附加到结果

最终迭代匹配第三个子句，设置X=6并返回[6,6]

然后展开堆栈：

从 [6,6] 中删除第一个元素并追加 1 -> returns [6,1]（第四次调用）
前置 1 -> returns [1,6,1]（第三次调用）
前置 1 -> returns [1,1,6,1]（第二次调用）
将 2 附加到尾部 -> returns [1,6,1,2]（第一次调用）

最终值为 [1,6,1,2]

在您的第二个示例中，第一个子句仅用于第一个元素。请注意，由于适当的列表以空列表结尾，因此模式匹配 [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>

Erlang 理解递归

Erlang understand recursion

erlang

recursion