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よりも遅い場合があります。
なるほどなるほど。
こちらから、Elixirのシンタックスハイライトきくのどれなのだろう、と投稿してみましたが、Qiitaくらいなのですね?なるほど...