# 遞迴思考

## 1. 理解函式

函式就是你丟問題給它，它就會幫你解決問題。
一般的函式你就是很直觀的寫下去就好，例如：

int max(int a,int b)
{
    if (a>b) return a;
    return b;
}

## 2. 理解遞迴函式

遞迴函式就是會呼叫自己的函式，通常會把原本的問題規模變小後再呼叫自己，自己收到更小的問題後再做一樣的事，直到問題變得足夠小就停止。

- 例如：
計算$n!(也就是1⨉2⨉...⨉n)$可以把問題變成計算$(n-1)!⨉n$。

int factorial(int n) //計算1⨉2⨉...⨉n
{
    if (n==1) return 1; //問題夠小
    
    //將問題化減乘計算(1⨉2⨉...⨉n-1)⨉n
    int ans=factorial(n-1)*n;
    return ans;
}

## 3. 如何證明

為什麼是對的？可以用數學歸納法證明。簡單來說，你只要證明：
- 若小的問題得到的答案是對的，轉換成大的問題也會是對的(轉換過程是對的)
- 問題足夠小時的答案是對的

那麼足夠小的會是對的，而且比足夠小再大一點的問題分割成足夠小的問題去算也會是對的，再大一點也會是對的以此類推。

## 4. 遞迴思考

1. 發現問題具有**可被分割為相同性質的小問題**特質
2. 先假設遞迴函式成立，思考如何將小問題的結果轉換成大問題的結果

「大事化小，return 小事」