# 台北康橋G8A 11/6 遞迴 Recursion

## 函式複習
*
1. void (無回傳值)

void print(int a[], int n) {
    for(int i=0;i<n;++i)
        cout << a[i] << endl;
}

int main() {
    int a[] = {1, 2, 3, 4, 5};
    print(a, 5);
}

2. int (回傳值為整數)

void print(int a) {
    cout << a << endl;
}

int square(int a) {
    return a*a;
}

int main() {
    int b = 10;
    // b = square(b);
    print(square(b));
}

## 費氏數列 (Fibonaccii Sequence)
$f_{n} = f_{n-1}+f_{n-2}, f_{0}=1, f_{1}=1$
$f(n)=f(n-1)+f(n-2)$
Initial states are important

int fibonaccii(int n) {
    if(n == 0 || n == 1)
        return 1;
    return fibonaccii(n-1) + fibonacci(n-2);
}

int main() {
    int n;
    cin >> n;
    cout << fibonaccii(n) << endl;
}

## 遞迴樹 (Recursion Tree)

## 階乘 (Factorial)

$5!=5\times4\times3\times2\times1=120$
Initial state: $0!=1$
Recursion: $f(n)=?\times f(n-1)$
$n\times (n-1)\times (n-2)\times ...\times 1=?\times(n-1)\times(n-2)\times...\times 1$

int factorial(int n) {
    .......
}

int main() {
    int x;
    cin >> x;
    cout << factorial(x) << endl;
}

## 排列 (Permutation)

窮舉所有排列組合，如果有n個人排隊，總共就有$n!$種排法。
（用迴圈寫非常複雜）

int main() {
	int chosen[4] = {0};
	int queue[4] = {0};
	for(int i=1;i<=3;++i) {
		chosen[i] = 1;
		queue[1] = i;
		for(int j=1;j<=3;++j) {
			if(chosen[j] == 1)
				continue;
			chosen[j] = 1;
			queue[2] = j;
			for(int k=1;k<=3;++k) {
				if(chosen[k] == 1)
					continue;
				chosen[k] = 1;
				queue[3] = k;
				for(int a=1;a<=3;++a) {
					cout << queue[a] << " ";
				}
				cout << endl;
				chosen[k] = 0;
			}
			chosen[j] = 0;
		}
		chosen[i] = 0;
	}
}

用recursion實做permutation

// chosen[i] == 1 -> i 被選過了
// chosen[i] == 0 -> i 沒被選過了
int chosen[] = {};
int queue[] = {};

int permutation(int n, int x) {
    // n個人排隊，已經排好x個
    if(n == x) {
        for(int i=1;i<=n;++i)
            cout << queue[i] << " ";
        cout << endl;
        return;
    }
    else {
        for(int i=1;i<=n;++i) {
            if(chosen[i] != 1) {
                queue[x+1] = i;
                chosen[i] = 1;
                permutation(n, x+1);
                chosen[i] = 0;
            }
        }
    }
}

int main() {
    permutation(5, 0);
}

## Recursion vs Loop

Loop的優點:比較快
Recursion的優點: 很簡潔

遞迴計算第40項：0.83秒
迴圈計算第一千萬項：0.04秒

int main() {
    int n;
    cin >> n;
    int f[100] = {1, 1};
    for(int i=2;i<=n;++i)
        f[i] = f[i-1] + f[i-2];
    cout << f[n] << endl;
}

## Memorization

把計算過的項先存在陣列裡面，可以避免recursion tree長得太龐大（空間換取時間）
速度是逼近loop

int arr[1000000] = {1, 1};

int f(int n) {
    if(arr[n] != 0)
        return arr[n];
    arr[n] = f(n-1) + f(n-2);
    return arr[n];
}

## Homework
http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b022