遞迴是大事化小，要記得小事化無
by 吳邦一 AP325

遞迴的概念

數學裡的遞迴

若一個函數直接或間接地用自己定義自己，它就是一個遞迴函數。

有很多數列或函數是採用遞迴的方式定義的，例如費氏數列：

取自 費波那契數

遞迴函數的特點在於不直接告訴你函數值是多少，而是讓你不斷轉移當前參數的狀態，直到當前的參數是有明確定義時為止。

從費氏數列觀察：

可以注意到我們求值的過程就好像先從上往下把問題拆分，最後再從底部的已知一路疊代回去。

另外一個例子是卡塔蘭數（Catalan number），它的定義是：

程式中的遞迴

而在程式中的遞迴，其實跟數學的差不多，「會直接或間接地呼叫自己」的函式就是遞迴函式。

值得一提的是，已經被數學定義好的遞迴函式都很好寫成程式

以下有幾個例子：

費氏數列：

long long fib(long long x) {
    if (x <= 1) return x;
    return fib(x - 1) + fib(x - 2);
}

卡塔蘭數（Catalan number）：

long long cat(long long n) {
    if (n <= 0) return 1;
    long long sum = 0;
    for (long long i = 0; i < n; ++i) {
        sum += cat(i) * cat(n - 1 - i);
    }
    return sum;
}

通常一般來說遞迴的使用場景是：

• 直接實作數學定義
• 結合圖論的概念，進行枚舉或搜尋