# 演算法與資料結構 遞迴簡述
###### tags: `Algorithm`
我們所熟悉的數學函式大多數都是由一行簡單的方程式所構成，以華氏溫度轉換成攝氏溫度為例子
> $C =5(F - 32)/9$

多數情況下只要我們有了式子，就可以簡單地寫出我們所需要的程式進行運算

但有一些數學運算式卻不是如此定義的，舉一個例子，有一個F函數，其定義域屬於非負整數集合，滿足以下情況
> $F(0) = 0$
> $F(X) = 2F(X - 1) + X^2$

從這個定義中我們可以發現，F(1) = 1, F(2) = 6, F(3) = 21，當一個函數使用自身函數作為定義時，就可以被稱作為遞迴(recursive)

而上方式子的舉例，使用C語言進行實作，我們可以表示為以下

int F(int x)
{
    if(X == 0)
    {
        return 0;
    }
    else
    {
        return 2 * F(X - 1) + X * X;
    }
}

而第三行和第四行我們所處理的，就是所謂的基準情況(Base case)，此時函數的值可以直接求出而不需要透過遞迴。

而 $F(X) = 2F(X - 1) + X^2$ 若失去了基本情況的假設，那麼便失去了意義，也就是一個遞迴若失去了基本情況，則遞迴本身不具有任何意義。

我們在透過遞迴求出最終答案時，每一個子問題最終需要回到基本情況，才能得出結果。

## 錯誤的遞迴使用，無效輸入
而我們設想一個情況，假設我們設X = -1時，丟入函式進行處理時，會發生甚麼樣的狀況

F(-1)會去呼叫F(-2)，F(-2)會去呼叫F(-3)，我們發現會永遠無法觸發基本情況的發生，最終導致不斷的呼叫，直到記憶體被占滿空間(Stack Overflow)。

而對於這樣的無效輸入，我們必須將其過濾，避免出現程式崩潰的情況發生

## 錯誤的遞迴使用，無效的定義
以下為一個遞迴程式

int Error(unsigned int N)
{
    if(N == 0)
    {
        return 0;
    }
    else
    {
        return Error( N / 3 + 1) + N - 1;
    }
}

我們仔細檢視第9行的式子 $Error( N / 3 + 1) + N - 1$ ，當我們呼叫Error(1)時，回傳的結果為Error(1)，這一件事情導致所有呼叫到Error(1)的函式都無法求得值。在遞迴程式設計時，需要注意其終止條件，避免程式崩潰，或是無法預期的錯誤產生。

## 列印數字
假設我們輸入一個正整數N，我們使用一個函式PrintOut(N)，並且這個函式對於印出數字，只能呼叫PrintDigit，這個函式一次只能印出一個數字，而這個問題，我們有一個非常簡單的解法，假設要印出 12345 ，我們先印出1234，然後在印出5，對於印出5，我們可以很簡單的使用PrintDigit(N % 10)處理，剩下的問題我們可以透過遞迴進行處理。

但這只處理了一般的情況，我們仍然需要確保這個程式在面對所有情況下，都可以觸發基本情況。假設0 <= N <= 10，而我們的基本情況就是PrintDigit(N)，這麼一來，我們便處理完畢所有情況。

void PrintOut(unsigned int N)
{
    if(N >= 10)
    {
        PrintOut(N / 10);
    }
    PrintDigit(N % 10);
}

而這個程式，其實還可以再進行優化，將N % 10優化為N - [N / 10] * 10，原因在於mod的操作相當耗費系統資源。

## 遞迴與歸納法，證明我們可以相信遞迴
我們使用歸納法對於上述列印數字給出嚴謹的證明

定理:
對於所有N >= 0，數字的遞迴列印是正確的

證明:
當N只有一位數字時，此程式必然正確，只呼叫了PrintDigit。
設PrintOut對所有N在對所有k位數，k屬於任意有理數，為正確的。

k + 1位數字可以透過前k位數字和一位最低位數字表示，前k數字恰等於N / 10，由於歸納法假設前k位數字可以被正確的列印出來，而最後一位數為N % 10，因此可以列印出任意k + 1位數
由數學歸納法，此證明完畢。

回想一下高中所學的數學歸納法，就會發現這個證明雖然看起來很奇怪，卻十分的正確，事實上他就是對於這個演算法的描述。

他描述的即為這個演算法的行為，在同一個問題中，所有子問題都可以假設執行正確，遞迴只需把所有的仔問題結果進行結合形成現行問題的解。而我們之所以確保他是正確的，其根據即是數學歸納法，而數學歸納法屬於完全嚴謹的演繹推理法，因此可以相信他是正確的

而根據上述，我們可以給出遞迴的第三個法則。

3.設計法則(design rule): 假設所有的遞迴呼叫都可以執行。而這是一個重要的法則，因為有了這一條法則，我們在設計遞迴程式設計時，不需要知道其中的細節，不必追蹤遞迴的細部呼叫。

## 遞迴的主要問題
遞迴主要的問題是記憶體空間的使用，雖這些記憶體使用十分合理，且可以幫助我們寫出更加簡潔的程式碼，但遞迴絕不應該是作為簡單for迴圈的替代物，之後我們將會討論遞迴涉及的記憶體空間的使用。

## 結論，遞迴設計準則
當我們在設計遞迴程式時，應該考慮以下四個基本原則
1. 基準情況(Base case): 必須存在某一些情況，他不需要經過遞迴就可以求出其結果
2. 不斷推進(making progress): 對於那些需要經由遞迴求得解的情況，每一次的遞迴呼叫必須要使求解的過程項基本情況推進。
3. 設計法則(Design rule): 假設所有遞迴呼叫都可以執行
4. 合成效益法則(compound interest rule): 在求解一個問題時，若子問題已經在先前的遞迴呼叫中求出解，不要在遞迴呼叫中不斷重複計算(可使用動態規劃解決)。