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」