エリクシール末尾呼び出し再帰関数

Question

私は、リスト内の偶数を検出し、数値のみを使用して新しいリストを返します。この機能を持っている：

def even([]), do: [] 

    def even([head | tail]) when rem(head, 2) == 0 do 
    [head | even(tail)] 
    end 

    def even([_head| tail]) do 
    even(tail) 
    end 

は、このすでに末尾呼び出し最適化されていますか？あるいは、すべての節が最後に自分自身を呼び出す必要がありますか？（「偶数」関数の2番目のバージョンはありません）もしそうでなければ、どのようにして再帰呼び出しを行うようにリファクタリングすることができますか？

これはフィルタやリダクションで行うことができますが、私はそれを試してみたかったのです。

Answer 1

2番目の句の最後の呼び出しがリストの前置き操作であり、それ自体の呼び出しではないため、この関数は末尾再帰的ではないということは間違いありません。このtail-recursiveを行うには、アキュムレータを使用する必要があります。累積は逆順で行われるため、最初の句ではリストを逆にする必要があります。

def even(list), do: even(list, []) 

def even([], acc), do: :lists.reverse(acc) 

def even([head | tail], acc) when rem(head, 2) == 0 do 
    even(tail, [head | acc]) 
end 

def even([_head| tail], acc) do 
    even(tail, acc) 
end 

しかし、Erlangで、あなたの「ボディ再帰」のコードを自動的に最適化され、最後に:lists.reverseコールを行い末尾再帰ソリューションよりも遅くないかもしれません。 Erlangのドキュメンテーションでは、このような場合に2つの結果のどちらをよりクリーンなコードに書くかを推奨しています。

lists:reverse/1の呼び出しに続いて逆にリストが正しい順序でリストを作成し、本体再帰関数より速い構築末尾再帰関数を使用して、神話によります。その理由は、ボディ再帰関数がテール再帰関数よりも多くのメモリを使用するからです。

これはR12Bの前にある程度真実でした。 R7Bの前にはさらに真実でした。今日はそうではありません。ボディ再帰関数は、通常、テール再帰関数と同じ量のメモリを使用します。テール再帰型またはボディ再帰型のどちらが高速であるかを予測することは、一般的には不可能です。したがって、あなたのコードをきれいにするバージョンを使用してください（ヒント：通常は本体再帰バージョンです）。

テールとボディの再帰についての詳細は、Erlang's Tail Recursion is Not a Silver Bulletを参照してください。

Myth: Tail-Recursive Functions are Much Faster Than Recursive Functions.