再帰 の

再帰について

再帰関数とは、自分自身を呼び出す関数のことです。

再帰関数には、少なくとも1つの_ベースケース_と、少なくとも1つの_再帰ケース_が必要です。

_ベースケース_は、関数を再度呼び出さずに値を返します。_再帰ケース_は関数を再度呼び出し、そのときに引数を変更して、いずれベースケースに一致するようにします。

たいていの場合、それぞれのケースはそれぞれの関数節に書きます。

# base case
def count([]), do: 0

# recursive case
def count([_head | tail]), do: 1 + count(tail)

再帰関数には、ベースケースを複数持たせることも、再帰ケースを複数持たせることもできます。たとえば、フィボナッチ数列は、ベースケースを2つ持つ再帰的な数列です。

def fibonacci(0), do: 0
def fibonacci(1), do: 1
def fibonacci(n), do: fibonacci(n - 1) + fibonacci(n - 2)

配列の中に、ある値xが何回現れるかを数えるには、再帰ケースが2つあります。

def count_occurrences([], _x), do: 0
def count_occurrences([x | tail], x), do: 1 + count_occurrences(tail, x)
def count_occurrences([_ | tail], x), do: count_occurrences(tail, x)

再帰によるループ

Elixirでは、不変性のため、ループを命令型言語とは違う書き方で書きます。たとえば、ループはたいてい次のようになります。

for(i = 0; i < array.size; i++) {
  # do something with array[i]
}

関数型言語では、i++を呼び出すようにiを変更することはできません。そのため、ループは再帰を使って実装する必要があります。

Elixirでforループに相当するものは、次のようになります。

def loop([]), do: nil

def loop([head | tail]) do
  do_something(head)
  loop(tail)
end

実際には、配列やその他の列挙可能なデータ構造を繰り返し処理するときは、ほとんどの場合Enumモジュールを使います。内部的には、Enumモジュールの関数は再帰を使って実装されています。

無限実行

再帰関数は、実装を誤ると、結果を永遠に返さないことがあります。これは問題になることがあります。というのも、関数が呼び出されるたびに、VMが結果を返すべき場所（コールスタック）への参照がメモリに保存されるからです。再帰関数が無限に自分自身を呼び出すと、メモリを使い果たしてVMがクラッシュする可能性があります（スタックオーバーフローエラー）。Elixirが動作するErlang VMは、再帰と信頼性のために特別に最適化されているので、無限再帰のエラーが明らかになったりクラッシュが起きたりするまでには、長い時間がかかることがあります。

この無限実行の問題は、次のことが原因で起こります。

• ベースケースの実装を忘れている。
• ベースケースを最初の節として定義していない。
• 再帰呼び出しのときに引数を適切に変更しておらず、そのためベースケースに永遠に到達しない。