Elixir

Elixir: 再帰の末尾呼び出し最適化について

gumi TECH Blog「Elixir入門 09: 再帰」は、Elixirの再帰によるループについて解説しています。本項は、再帰の末尾呼び出し最適化について補います。


再帰呼び出しのコード例

前出「Elixir入門 09」の「reduceとmapのアルゴリズム」の項には、リスト要素をすべて2乗するつぎのようなコード例が示されています。再帰呼び出しの組み立てを知るには、わかりやすい例です。

defmodule Sum do

def square([]), do: []
def square([head | tail]), do:
[head * head | square(tail)]
end

iex> Sum.square([1, 2, 3, 4])

[1, 4, 9, 16]

ただ、このコードには無駄があります。最後に再帰呼び出しした関数から戻り値を受け取るまで、リストがつくれないことです。上の例では、処理がつぎのように進みます。

Sum.square([1, 2, 3, 4])

[1 * 1 | Sum.square([2, 3, 4])]
[1 | [2 * 2 | Sum.square([3, 4])]]
[1 | [4 | [3 * 3 | Sum.square([4])]]]
[1 | [4 | [9 | [4 * 4 | Sum.square([])]]]]

最後の戻り値を得て、ようやくリストが確定するわけです。

[1 | [4 | [9 | [16 | []]]]]

[1 | [4 | [9 | [16]]]]
[1 | [4 | [9 , 16]]]
[1 | [4 , 9 , 16]]
[1, 4 , 9 , 16]


再帰の末尾呼出しを最適化する

関数の最後の処理で再帰呼び出しすることは「末尾再帰」と呼ばれます。その戻り値を待たずに済めば、処理が最適化できるでしょう。そのためには、処理をあとの関数に任せてしまえばよいのです。

つぎのように、表立つ関数(Sum.square/1)を起き、内部的(defp)には引数(accumulator)をひとつ増やします。このリストに自分までの処理を加えて、再帰呼び出しする関数に渡してしまうのです。

defmodule Sum do

def square(list), do: square(list, [])
defp square([], accumulator), do: accumulator
defp square([head | tail], accumulator), do:
square(tail, [head * head | accumulator])
end

こうすれば、戻り値を待つことなく、リストは逐次組み立てられます。再帰呼び出しの関数に渡される引数の変化は、つぎのとおりです。

Sum.square([1, 2, 3, 4])

[2 , 3 , 4], [1 * 1 | []]
[3 , 4], [2 * 2 | [1]]
[4], [3 * 3 | [4, 1]]
[], [4 * 4 | [9, 4, 1]]
[16, 9, 4, 1]

ただし、お気づきのように順序が逆です。最後に、Enum.reverse/1でもとに戻しましょう。

defmodule Sum do

def square(list), do: Enum.reverse(square(list, []))
defp square([], accumulator), do: accumulator
defp square([head | tail], accumulator), do:
square(tail, [head * head | accumulator])
end

[追記] 戻り値を呼び出しもとが待つ場合には、スタックに戻り先の情報をもちます。再帰が深くなりすぎてしまうと、スタックオーバーフローになりかねません。待たずに済むようにすれば、仮想マシンは現在のスタックフレームをすみやかに削除してくれます。これは、コンパイラによって行われる最適化です。

また、Enum.reverse/1が呼び出すErlangのlists:reverse/2は、組み込み関数(BIF)としてCで書かれている処理の速い関数です。


参考

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

Memory Usage in Recursion

[erlang-questions] Tail call optimization