再帰 の

再帰について

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

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

基底ケースは、関数を再度呼び出すことなく値を返します。 再帰ケースは、いずれ基底ケースに一致するように入力を変更しながら、関数を再度呼び出します。

配列の要素を数える例を見てみましょう。

def count:
  if length == 0 then
    0                       # base case
  else
    1 + (.[1:] | count)     # recursive case
  end;

([] | count),           # => 0
([11, 22, 33] | count)  # => 3

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

def fibonacci:
  if . == 0 then
    0
  elif . == 1 then
    1
  else
    (. - 1 | fibonacci) + (. - 2 | fibonacci)
  end;

10 | fibonacci          # => 55

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

def count_occurrences(x):
  if length == 0 then
    0
  elif first == x then
    1 + (.[1:] | count_occurrences(x))
  else
    (.[1:] | count_occurrences(x))
  end;

[11, 22, 33, 22, 44] | count_occurrences(22)    # => 2

実際には、配列やその他の列挙可能なデータ構造を繰り返し処理するときは、mapやreduceのような組み込み関数を使うか、[.[] | select(...)]のようにストリームを使うことがほとんどです。 内部的には、一部の組み込み関数は再帰を使って実装されています。

無限再帰

再帰関数は、実装を誤ると、結果をいつまでも返さないことがあります。 これは問題になり得ます。関数が呼び出されるたびに、仮想マシンが結果を返すべき場所（コールスタック）への参照がメモリに保存されるからです。 再帰関数が無限に自分自身を呼び出すと、メモリを使い果たし、スタックオーバーフローエラーで仮想マシンがクラッシュする可能性があります。

この無限再帰の問題は、次のような原因で起こります。

• 基底ケースの実装を忘れている。
• 基底ケースを最初の条件節として定義していない。
• 再帰呼び出しのときに引数を正しく変更しておらず、そのために基底ケースに到達しない。

末尾呼び出しの最適化

Wikipediaで説明されているとおりです。

末尾呼び出しとは、手続きの最後の動作として行われるサブルーチン呼び出しのことです。 末尾呼び出しの対象が同じサブルーチンである場合、そのサブルーチンは末尾再帰であると言われます。

上で実装したfibonacciの実装を考えてみましょう。 その再帰ケースは、自分自身を2回呼び出します。 関数が最後に行わなければならない動作は、足し算です。 最後の動作が自分自身への呼び出しではないため、この関数は再帰的ではありますが、末尾再帰ではありません。

一部の言語では_末尾呼び出しの最適化_が実装されており、末尾呼び出しはコールスタックに新しいフレームを追加することなく、現在のスタックフレームを再利用できます。 これには、厄介なスタックオーバーフローを防げるだけでなく、パフォーマンス上の利点もあります。

jqにも末尾呼び出しの最適化は実装されていますが、それは0アリティの関数に限られます。 これを活用する方法は、何らかの状態を入力として受け取る「内側の」0アリティ関数を定義することです。 内側の関数は、必要に応じて状態を変更し、新しい状態を末尾再帰呼び出しに渡すことができます。 外側の関数は初期状態を作り、それを内側の関数に渡して再帰を開始します。

末尾再帰のfibonacci関数は、それまでに計算した数列を状態の一部として保持することで実装できます。

def fibonacci:
  def _fib:
    # input: {limit: number, series: array}
    if (.series | length - 1) >= .limit then
      .series[.limit]                                   # base case
    else
      .series += [.series[-1] + .series[-2]] | _fib     # recursive case
    end;
  {limit: ., series: [0, 1]} | _fib;

10 | fibonacci          # => 55