Recursion (遞迴) 簡介 - PHP 範例

12月 22 2020 Data Structure and Algorithm 10 分钟讀完 (大概 1508 字)

前言

還記得某強者朋友 Chris 曾說…

遞迴只應天上有, 凡人還請用迴圈

嗯… 用不用我們再慢慢研究, 但了解一下總是可以的吧？

# 簡介

Recursion (遞迴) 是一種透過將大問題分成小問題, 在逐一突破解決的方法, 就跟我們面對人生的困難一樣, 總是要先尋找小確幸, 再從小確幸中找到前進的勇氣, 然後再一點一點的逐一突破困難… 就跟追女朋友一樣, 總是要先… 咦, 不是要講 recursion 嗎？哦! 不好意思離題了。
通常, recursion 又被稱為 呼叫自己的 function, 沒錯, 我也覺得很怪！

那你可能會問, 阿不停的呼叫自己, 有完沒完？

沒錯！所以當我們在寫一個 recursion function 時, 必須具有以下要點：

每一次的 recursion 呼叫, 都必須要把問題變得更小, 聽不懂? 那下面看範例會比較清楚。
必須要為 recursion function 設定一個終點, 且這個終點是不需要任何的 recursion 呼叫就可以解決自己的問題, 不然就沒完沒了了
不可以有循環出現, 這也是上一個要點所要避免的事情, 不然就跟無限 loop 一樣, 死機了

接下來我們來舉幾個範例, 如果看不懂可以跳過去, 挑看得懂的看, 因為我一開始看也是一臉矇逼, 比你還矇

# 實例

# factorial

“factorial” (階乘) 在數學中相當熱門, factorial of 5, 在數學中又寫成 5!, 等於 5 * 4 * 3 * 2 * 1

以此類推:
4! 會等於 4 * 3 * 2 * 1
3! 會等於 3 * 2 * 1
2! 會等於 2 * 1
1! 會等於 1

眼尖的你是否發現了什麼？沒發現嗎？好, 我當初也沒發現, 沒事沒事…
這樣你都能發現？哇靠, 你真是有 programmer 的 DNA 啊！不, 簡直是圖靈在世！馬的我就是一個廢物, 我都沒發現。
那就是 5! = 5 * 4!

以此類推:
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1

等等… 為啥 0! = 1 ? 這不太合理吧？馬的沒錯我當初也是這樣想… 不過研究了一下才知道人家數學家定義這個叫做 empty product, 值就是 1 沒得說, 不要問原因無可奉告, 可以參考一下 Wiki

好這不是重點, 重點是你又發現了嗎？那就是從上面的規則中, 可以歸納出
n! = n * (n-1)!

好, 規則出現了！現在我們來寫一個 PHP 的 recursion function 來求得 factorial

function factorial(int $n): int {
   if ($n == 0)
    return 1;

   return $n * factorial($n - 1);
}

還記得上面提到的 recursion 要點 (1) 嗎？在每一次的 recursion, 問題都會變小, 上面的 example 就可以呈現這一點

在每一次的 recursion, $n 都會減 1

而 $n == 0 的 if 判斷正是要點 (2), 設定一個終點, 以避免無限循環

假設我們使用 factorial(3), 那大概會依序拆成以下步驟

3! = 3 X 2! (將問題 break 並往下 pass, return 3 * factorial(3 - 1))
2! = 2 X 1! (將問題 break 並往下 pass, return 2 * factorial(2 - 1))
1! = 1 X 0! (將問題 break 並往下 pass, return 1 * factorial(1 - 1))
0! = 1 (到達終點, 回傳 1)
1! = 1 X 1 = 1 (回傳結果 1 給上一個 recursion)
2! = 2 X 1 = 2 (回傳結果 2 給上一個 recursion)
3! = 3 X 2 = 6 (執行 3 * 2 = 6, 最終結果)

如下示意圖:

好啦, 那你問, 我用 loop 行不行? 非得要 recursion?

的確, 使用 loop 也是可以求得 factorial 的

<?php
function factorial(int $n): int { 
    $result = 1; 

    for ($i = $n; $i > 0; $i--) {
      $result *= $i; 
    } 

    return $result; 
}

那, 為什麼要使用 recursion 呢？

recursion 是用來解決更複雜的問題, 比如說, 你想要列出某個資料夾底下的所有資料夾, 包含子資料夾, 但是你並不知道共有幾層, 這就是一個非常適合用 recursion 來解決的問題。

然而, recursion 是使用 call stack 來管理 function call, 也就是像 Stack 資料結構一樣, LIFO (last in first out), 這使得 recursion 會比 loop 使用更多的 memory 以及時間

並且, loop 的每一個 step 都會有其結果, 但 recursion 會需要跑到最後一次的 recursion, 再依序往前推 (first in last out)

# Fibonacci

Fibonacci 數列是一組特別的整數順序, 每一個數都可由前兩個數計算得來, 數列中全部都是質數, 例如 1, 2, 3, 5, 7, 11 …
而 Fibonacci 有個公式, 如下：

可以寫成一個 PHP function

<?php
function fibonacci(int $n): int { 
    if ($n == 0) { 
    return 1; 
    } else if ($n == 1) { 
    return 1; 
    } else { 
    return fibonacci($n - 1) + fibonacci($n - 2); 
    }

沒錯, 我們在一個 function 裡頭呼叫了兩個 recursion function

之後我們再來討論不同類型的 recursion

# GCD

GCD (Greatest Common Division), 最大公因數, 比如 12 的因數有 1, 2, 3, 4, 6, 而 8 的因數有 1, 2, 4, 那 12 跟 8 的最大公因數就是 4

抱歉, 我知道這節不是數學課, 其實我是講給我自己聽的, 哈哈哈哈哈哈！

所以在數學中若要求得兩數的最大公因數, 有個公式如下：

那如果用 PHP 來寫的話, 如下：

<?php
function gcd(int $a, int $b): int { 
    if ($b == 0) { 
     return $a; 
    } else { 
     return gcd($b, $a % $b); 
    } 
}

這又是另外一種類型的 recursion, 我們不從終點一路 return 回起點, 反之, 直接在終點 return 了 value
這也是比較理想的 recursion 方式

# 結論

本篇 recursion 的簡介就到此結束, 接下來我們會講不同類型的 recursion

# 參考來源

PHP 7 Data Structures and Algorithms: Implement linked lists, stacks, and queues using PHP

# Questions and Answers

何謂質數?

大於 1 的自然數中, 無法被除了 1 和自身之外的數整除, 稱為質數

何謂 Fibonacci Sequence?

一組由質數所組成的數列

何謂 GCD (Greatest Common Division)?

最大公因數, 比如 12 的因數有 1, 2, 3, 4, 6, 而 8 的因數有 1, 2, 4, 那 12 跟 8 的最大公因數就是 4

#Recursion