再帰関数

再帰

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

_再帰関数_には、少なくとも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(...)]のようにストリームを使うのが一般的です。 内部では、一部の組み込み関数が再帰を使って実装されています。