用 遞迴 (Recursion) 由零實作 RegEx 解析器（遲來的README）

Recursion 在現實生活中很少見，展示的例子一般有 斐波那契數列 (Fibonacci sequence) 、堆棧(stack)的先入後出(first in last out)、遍歷上色問題(cell painting) 等。

2009年我用「間接遞迴 (Indirect Recursion)」（當時我稱之為「多重遞迴 Double Recursion」) ，輔以 function pointers 實作了一個 正則表達式 (Regular Expression) 的 解析器 (parser)。Google 的結果告訴我，用這方法實作是首創。稍後有幾間公司連絡我，把我的算法整合到他們的內部程式庫，應用例子有 web-based coding sandbox 和 網頁的 script interpreter engine。

Recursion 的概念，簡單來說就是「自己叫自己」。結構包括兩部份：終結條件(terminating condition) 和 遞迴的表達式 (expression)。

簡單例子如下：

上面僅用兩行程式碼，便能計算 (1 * 2 * 3 * ... * n-1 * n) 的結果：

> mul(1)

1

> mul(2)

2

> mul(3)

6

> mul(4)

24

> mul(5)

120

遞迴的好處 是 程式碼很簡練(compact)，編譯後的二元碼很小，例如我的 regex engine 只有 5 KB，Lite version 更少於 2KB。普通一部家用電腦的記憶體，可平衡執行成千上萬個實體。

遞迴的缺點是難以預測需要多少記憶體、難偵錯、稍一不慎便會墮入無限迴旋(infinite loop)。現實世界的其中一個解決辦法，是 Circuit Breaker。

「間接遞迴」(或「多重遞迴」) 的概念為：

        A(x) --> B(y) --> ... --> A(z) 

用在正則表達式 ，使用時機在於括弧，例如：

        pattern = "abc(def(gh){2,4})+ijk\1*"

可被分解為：

        pattern1 = "abcX+ijkZ*"

        X = "defY{2,4}"        

        Y = "gh"

        Z = "\1" = X

換句話說每次遇上 '('，就可以用遞迴進入下一層；然後每見到 ')' 就從遞迴回傳至上一層。

每一層遞迴需要叫用什麼函式，是根據遇上的符號，用 switch case 加 函數指標 (function pointers)達成。

我的 C 程式庫展示例子在2009年上載到 Source Forge:

https://sourceforge.net/projects/crx/ 

以後若有機會更新，會放到 github:

https://github.com/hexabox-dev/crx