遞迴（Elixir從零開始系列 05）（鼠年全馬鐵人挑戰 W06）

這是 w3HexSchool 鼠年全馬鐵人挑戰 Week 6 唷

這是 Elixir 從零開始系列 05 唷

前言

遞迴在 Elixir 中是一個很重要的部分，讓我們趕緊來瞧瞧

不可變特性（Immutability）

對於 Functional programming language （Elixir 也是成員之一）來說，有一個特性叫不可變特性（Immutability），什麼是不可變特性呢？在 Elixir 中所有的資料都是不可修改的，像是所有的函數回傳一定都是回傳一個新的值，那要修改一個特定變數呢？

iex(1)> var1 = 20
20
iex(2)> var1 = 40
40

如以上範例，看起來我們更改了 var1 的值，但實際上內部作業不是這樣的

要更改變數的唯一方法就是給予同樣的變數名稱但是賦予它新一個記憶體位置

由於不可變特性的關係， Loop 在 Elixir 或者說 Functional programming language 中不存在，舉例子來說好了

For loop

int[] a1 = new int[10];
for (int i = 0; i < 10; i++)
{
    a1[i] = i;
}

While loop

int n = 0;
while (n < 5)
{
    Console.WriteLine(n);
    n++;
}

以上 C# 兩個 Loop 範例，我們變動了 i 、n 和 array 的值，這在指令式程式設計是一個很常見的用法，但在 Elixir 裡面可不行這樣做喔，取而代之的是遞迴

Rescursion

今天假設我們要設計一個 Loop，功能為輸入次數與字串，輸出為次數*字串，那我們可以這樣做

defmodule Recursion do
 def print_multiple_times(msg, 1) do
  IO.puts msg
 end

 def print_multiple_times(msg, n) do
  IO.puts msg
  print_multiple_times(msg, n - 1)
 end
end

我們可看到結果

iex(1)> Recursion.print_multiple_times("hello",3)
hello
hello
hello
:ok

這就是一個利用遞迴取代迴圈的作法，不斷的呼叫 print_multiple_times(msg, n) 來達到迴圈的效果，同時間也設立一個 print_multiple_times(msg, 1) 作為遞迴停止的條件，我抓了上面的範例並加了註解

iex(1)> Recursion.print_multiple_times("hello",3)
hello # print_multiple_times(msg, n)
hello # print_multiple_times(msg, n)
hello # print_multiple_times(msg, 1)
:ok

Tail function calls

你們可能會有一個問題是，我每一個 Loop 都用遞迴取代，當有遞迴次數很多的時候，那有可能會發生 stack overflow，針對這樣的問題，Elixir 提供了一個解決方案 tail-call optimization，當函式的最後一行是呼叫自己或是另一函式，該行我們叫它 Tail call，當呼叫到該行時，此時 Elixir 並不會新產生一個堆疊空間（Stack space）來配置給新函式，而是利用 JUMP 的概念在原來的堆疊空間操作新的函式，利用此一方法，就不會有不斷新增新的堆疊空間問題，我們就可以毫不羞恥的使用遞迴啦（誤 XD

以下是一個 tail call

def fun(...) do
    ...
    if something do
        ...
        another_fun(...) #Tail call
    end
end

以下不是一個 tail call，因為最後一行不是單純函式呼叫

1
2
3

def fun(...) do
    1 + another_fun(...) # Not a tail call
end

前言

不可變特性（Immutability）

Rescursion

Tail function calls

參考資料