遞迴 在

關於 遞迴

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

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

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

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

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(...)]。 在底層，有些內建函式就是用遞迴實作的。

無窮遞迴

遞迴函式如果實作得不正確，可能永遠不會回傳它的結果。 這可能會造成問題，因為每次呼叫函式時，記憶體中都會儲存一個參考，指出虛擬機器應該把結果回傳到哪裡（在呼叫堆疊上）。 如果一個遞迴函式無止境地呼叫自己，就可能會耗盡記憶體，導致虛擬機器因堆疊溢位錯誤而崩潰。

這個無窮遞迴的問題可能由以下原因造成：

• 忘記實作基本情況。
• 沒有把基本情況定義成第一個子句。
• 進行遞迴呼叫時沒有正確修改引數，因此永遠到不了基本情況。

尾呼叫最佳化

正如維基百科所述：

尾呼叫是指以程序的最後一個動作來執行副程式呼叫。 如果尾呼叫的目標是同一個副程式，就稱這個副程式為尾遞迴。

看看上面實作的fibonacci。 它的遞迴情況會呼叫自己兩次。 函式最後需要執行的動作是加法。 由於最後的動作不是呼叫自己，所以這個函式是遞迴的，但不是尾遞迴。

有些語言實作了_尾呼叫最佳化_，讓尾呼叫可以重複使用目前的堆疊框架，而不必在呼叫堆疊上新增一個框架。 除了能避免可怕的堆疊溢位之外，這還能帶來效能上的好處。

jq確實有實作尾呼叫最佳化，但只適用於零參數函式。 要利用這一點的方法，就是定義一個「內層」的零參數函式，讓它以某種狀態作為輸入。 內層函式可以視需要修改狀態，並把新的狀態傳給尾遞迴呼叫。 外層函式則建立初始狀態，並把它傳給內層函式來開始遞迴。

一個尾遞迴的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