遞迴 在

關於 遞迴

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

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

_基本情況_會直接回傳一個值，不再呼叫函式。_遞迴情況_則會再次呼叫函式，並修改輸入，讓它最終能符合基本情況。

很多時候，每種情況會各自寫成一個函式子句。

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

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

一個遞迴函式可以有很多個基本情況，也可以有很多個遞迴情況。舉例來說，費氏數列就是一個有兩個基本情況的遞迴數列：

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

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

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 模組裡的函式就是用遞迴實現的。

無限執行

如果實作方式不對，遞迴函式可能永遠不會回傳結果。這會造成問題，因為每次呼叫函式時，記憶體中都會儲存一筆參考，記錄虛擬機器應該把結果回傳到哪裡（也就是呼叫堆疊上）。如果遞迴函式無限地呼叫自己，就可能耗盡記憶體，導致虛擬機器崩潰（也就是堆疊溢位錯誤）。Elixir 所運行的 Erlang 虛擬機器特別針對遞迴和可靠性做了最佳化，因此無限遞迴的錯誤可能要很久才會顯現，或是很久才會崩潰。

這種無限執行的問題可能由下列原因造成：

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