erlang - Erlang 中的尾递归

Question

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

我的实现是尾递归的吗？如果不是，我该如何实现？

提前致谢

Answer 1

您的实现不是尾递归的，因为在计算尾部时追加必须保持在列表的头部。为了使函数成为尾递归函数，返回值不得依赖于函数调用返回的值以外的值。

你可以这样重写它:

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 按顺序评估子句，并且由于终止子句通常更具体，不太具体的递归子句将隐藏它们，从而防止函数返回，这很可能不是您想要的行为。