Erlang中的尾递归

Question

Erlang中的尾递归

3

我很难理解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([])  ->
    [].

我的实现是否是尾递归的？如果不是，我该如何使其成为尾递归？

提前感谢。

- dagda1

1

你是否在想你的 append 函数是否是尾递归的？我可以问一下它的作用吗？ [Record|Database] 不也能很好地工作吗？ - Samir Talwar

我感觉他为了简洁而省略了实际功能。 - Jeremy Wall

引入一个临时变量，你会发现你的追加操作不是尾递归的：append([H|T]) -> T1 = append(T), [H|T1]; - Zed

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jeremy Wall · Accepted Answer

由于append需要在计算尾部时保留列表的头部，因此您的实现不是尾递归的。要使函数成为尾递归，返回值不能依赖于除从函数调用返回的值之外的任何值。

您可以这样重新编写：

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

注意，一旦尾递归调用发生，所有工作都完成了。因此，追加函数可以“忘记”函数体中的所有内容，只需要记住传递到下一次调用中的参数值。

还要注意，我将终止子句放在递归子句之前。Erlang按顺序评估子句，并且由于终止子句通常比不太具体的递归子句更具体，因此递归子句会隐藏它们，从而防止函数返回，这很可能不是您想要的行为。