尾巴递减在Erlang [英] Tail recursion in Erlang

问题描述

我有以下eunit测试：

  db_write_many_test（） - > 
 Db = db：new（），
 Db1 = db：write（francesco，london，Db），
 Db2 = db：write（lelle，stockholm，Db1），
 ？assertEqual（[{lelle，stockholm}，{francesco，london}]，Db2）。 
  

这里是我的实现：

  -module（db）。 
 -include_lib（eunit / include / eunit.hrl）。 
 -export（[new / 0，write / 3]）。 
 
 new（） - > 
 []。 
 
 write（Key，Value，Database） - > 
 Record = {Key，Value}，
 [Record | append（Database）]。 
 
 append（[H | T]） - > 
 [H | append（T）]; 
 append（[]） - > 
 []。 
  

我的执行尾是否递归，如果没有，我该怎么做？

提前感谢

解决方案

您的实现不是尾递归递归的，因为附加必须持有列表的头部，同时计算尾巴。为了使函数具有尾递归，返回值不能依赖于函数调用返回的值以外的值。

可以将其改写为所以：

  append（Acc，[]） - > %%终止; 
 Acc; 
 append（Acc，[H | T]） - > 
 Acc2 = Acc ++ dosomethingto（H）; %%也许你的意思是这是你的写功能？ 
 append（Acc2，T）; %% tail rercursive 
  

请注意，一旦尾部递归调用发生，所有的工作都完成。因此，附加功能可以在函数体中忘记，只需要记住下一次调用的参数值。

还要注意，我将finally子句放在递归子句之前。 Erlang按顺序评估子句，由于终止子句通常更具体，较不具体的递归子句将隐藏它们，从而阻止函数永远不会返回，这绝对不是您希望的行为。

I am really struggling to understand tail recursion in Erlang.

I have the following eunit test:

db_write_many_test() ->
    Db = db:new(),
    Db1 = db:write(francesco, london, Db),
    Db2 = db:write(lelle, stockholm, Db1),
    ?assertEqual([{lelle, stockholm},{francesco, london}], Db2).

And here is my implementation:

-module(db) .
-include_lib("eunit/include/eunit.hrl").
-export([new/0,write/3]).

new() ->
    [].

write(Key, Value, Database) ->
    Record = {Key, Value},
    [Record|append(Database)].

append([H|T]) ->
    [H|append(T)];  
append([])  ->
    [].

Is my implementation tail recursive and if not, how can I make it so?

Thanks in advance

解决方案

Your implementation is not tail recursive because append must hold onto the head of the list while computing the tail. In order for a function to be tail-recursive the return value must not rely on an value other than the what is returned from the function call.

you could rewrite it like so:

append(Acc, []) -> %% termination;
    Acc;
append(Acc, [H|T]) ->
    Acc2 = Acc ++ dosomethingto(H); %% maybe you meant this to be your write function?
    append(Acc2, T); %% tail rercursive

Notice that all the work is finished once the tail recursive call occurs. So the append function can forget everthing in the function body and only needs to remember the values of the arguments it passes into the next call.

Also notice that I put the termination clause before the recursive clause. Erlang evaluates the clauses in order and since termination clauses are typically more specific the less specific recursive clauses will hide them thus preventing the function from ever returning, which is most likey not your desired behaviour.

这篇关于尾巴递减在Erlang的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！