遞迴函式

遞迴

遞迴函式是一種會呼叫自己的函式。

一個_遞迴函式_至少需要一個_基本情況_，以及至少一個_遞迴情況_。

基本情況會回傳一個值，而不會再次呼叫函式。 遞迴情況會再次呼叫函式，並修改輸入，讓它在某個時間點符合基本情況。

以下是一個計算陣列元素數量的範例。

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

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

一個_遞迴函式_可以有很多個_基本情況_，也可以有很多個_遞迴情況_。 例如費波那契數列就是一個有兩個_基本情況_的遞迴數列。

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

10 | fibonacci          # => 55

計算某個給定的值x在陣列中出現的次數，會有兩個_遞迴情況_。

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(...)]這樣使用資料流。 在底層，有些內建函式則是用遞迴實作的。