概念

有些人認為遞迴僅是在運行過程中，直接或間接地持續呼叫自己的一個函式。

然而，我認為遞迴的基本概念更深入，它是一種將一個大問題分解成多個子問題的方法，並透過遞迴或迴圈的方式來解決這些問題。因此，遞迴的關鍵不在於如何進行遞迴，而在於如何分割問題。

實作

void recursive(){
    recursive();
}

基本上，遞迴的基本概念就如上所示，但我們還需要添加終止條件，否則遞迴將無限進行下去，最終導致不可預測的結果。

Top-down

Top-down 是一種遞迴的實作方式，我們可以以計算階乘為例：

可以看出這可以整理成 的形式，程式碼如下

int f(int n){
    if(n == 0){
        return 1;
    }
    return f(n - 1) * n;
}

而上面有說，需要設置終止條件，而這邊的終止條件就是 的時候

Bottom-up

從 Top-down 算階乘的過程可以思考出：

• 呼叫
• 呼叫
• 呼叫
• 呼叫
• 呼叫
• 回傳
• 透過 算出答案
• 透過 算出答案
• 透過 算出答案
• 透過 算出答案
• 透過 算出答案

然而，我們可以思考一個問題：如果我們可以從 開始，然後一直計算到 ，是否能夠節省更多步驟呢？這就是 Bottom-up 的思維方式。以下是程式碼：

int f[0] = 1;
for(int i = 1;i <= 5;i++){
    f[i] = f[i - 1] * i;
}

可以看出，Bottom-up 的思維方式更直觀。然而，選擇使用 Bottom-up 前，必須確保在計算當前問題時，所需的所有子問題答案都已經計算完成，就像上面的階乘問題一樣，因為在計算 時， 必須已經被計算完成。

總結

遞迴是計算機科學中的一個重要概念，可用於解決各種問題，尤其是可以分解為較小子問題的問題。本文提供基本介紹和示例，對遞迴的基本原理以及兩種常見的實作方式（Top-down 和 Bottom-up）進行說明。

預告

明天應該會有這個章節的例題講解，不過難度不會太高，只是單純找一些題目讓大家可以更了解遞迴的概念。