[Elixir in Action]Erlang/Elixirの再帰計算におけるnon-tail recursionとtail recursion

ちょっと印象的だったので。

再帰計算を行う関数の最後が、別の関数呼び出しかどうか、という違いです。

non tail recursion

defmodule ListHelper do
  def sum([]), do: 0

  def sum([head | tail]) do
    head + sum(tail)
  end
end

https://github.com/sasa1977/elixir-in-action/tree/master/code_samples/ch03

tail recursion

defmodule ListHelper do
  def sum(list) do
    do_sum(0, list)
  end

  defp do_sum(current_sum, []) do
    current_sum
  end

  defp do_sum(current_sum, [head | tail]) do
    new_sum = head + current_sum
    do_sum(new_sum, tail)
  end
end

https://github.com/sasa1977/elixir-in-action/blob/master/code_samples/ch03/sum_list_tc.ex

Dive to source code

Elixirには、再帰表現をまとめたコードとして Enum.reduce(collection, acc, fun) なんかを提供しています。
この中身を少しみてみましょう。

Elixirの の再帰箇所は以下のように書かれています。

def reduce(collection, acc, fun) when is_list(collection) do
  :lists.foldl(fun, acc, collection)
end

Erlangの資料によると、 :lists.foldl(Fun, Acc0, List) はtail recursionとのこと。
こちら

foldl/3 is tail recursive and would usually be preferred to foldr/3.

ということは、 Enum.reduce(collection, acc, fun) はtail recursionなのですね。

コード追うと Enum.reduce/2 も Enum.reduce/3 を結局は呼ぶので、reduceはtail recursionで実装されていて、巨大なリストに対してもちゃんと再帰計算ができることを重視されているのですね。
Elixirの List.foldr/3 や List.foldl/3 もそれらを呼び出しているので、tail recursionなのですね。

利点として、このtail recursionの場合、メモリの消費を増やすことなく、無限に再帰呼び出しができると。
一方、これは手続き型な書き方な側面や、性能的にnon tail recursionよりも遅い場合があります。

なるほどなるほど。

---

[更新]20150806

Erlangの :lists.foldr(Fun, Acc0, List) を :lists.foldl(Fun, Acc0, List) に書き直しました。