# Recursion ###### 2020 Clang, 0w1 --- ### 遞迴  ---- ### 遞迴  ---- ### 遞迴 * 簡單來說就是用自己定義自己 * 有時可以將很複雜的概念描述得很簡潔 --- ### 失敗的定義：自然數 n 是自然數，若其一成立： * n = 1 * n = 2 * n = 3 * ... ---- ### 遞迴定義：自然數 n 是自然數，若其一成立： * n = 1 * 存在一個自然數 m 使得 n = m + 1 ---- 4 是自然數，因為： 1. 1 是自然數 2. 2 = 1 + 1, 所以 2 是自然數 3. 3 = 2 + 1, 所以 3 是自然數 4. 4 = 3 + 1, 所以 4 是自然數 --- ### 失敗的定義：祖先 A （男）是 B 的祖先，若其一成立： * A 是 B 的父親 * 存在 C 使得 A 是 C 的父親，而 C 是 B 的父親 * 存在 C, D 使得 A 是 C 的父親，C 是 D ..., D 是 B ... * ... ---- ### 遞迴定義：祖先 A （男）是 B 的祖先，若其一成立： * A 是 B 的父親 * 存在一個 B 的祖先 C 使得 A 是 C 的父親 ---- A -> C -> B 1. C 是 B 的父親，所以 C 是 B 的祖先 2. A 是 C 的父親，所以 A 是 B 的祖先 ---- A -> C -> D -> B 1. D 是 B 的父親，所以 D 是 B 的祖先 2. C 是 D 的父親，所以 C 是 B 的祖先 3. A 是 C 的父親，所以 A 是 C 的祖先 --- ### 費氏數列 0, 1, 1, 2, 3, 5, 8, 13, 21, ... ---- ### 遞迴定義：費氏數列 * f(0) = 0 * f(1) = 1 * f(n) = f(n - 1) + f(n - 2), if n > 1 ---- ### 一般式：費氏數列  * 缺點：需要高精度浮點數運算 --- ### 程式的遞迴 ```cpp void f(int n) { cout << n << ", "; f(n + 1); } f(0); // 0, 1, 2, 3, ... ``` ---- ### 遞迴倒數 ```cpp void f(int n) { if (n < 0) return; // 數到負的就該停了！ cout << n << ", "; f(n - 1); } f(5); // 5, 4, 3, 2, 1, ``` --- ### 遞迴函數基本要件 * 邊界條件：什麼時候可以停下來？ * 遞迴關係：這個值跟哪些值有怎樣的關係？ ---- ### 邊界條件：費氏數列 * f(0) = 0 * f(1) = 1 ---- ### 遞迴關係：費氏數列 當 n > 1： * f(n) = f(n - 1) + f(n - 2) --- ### 遞迴計算費氏數列 ```cpp int f(int n) { if (n == 0) return 0; // * f(0) = 0 if (n == 1) return 1; // * f(1) = 1 return f(n - 1) + f(n - 2); // * f(n) = f(n - 1) + f(n - 2) } ``` ----  ---- 有很多重複計算？ * 可以把算過的值存起來 * 當詢問計算過的值，直接查表回傳 ---- ```cpp int table[100000]; int f(int n) { if (table[n] != 0) return table[n]; // 非 0 代表算過了 if (n == 0) return 0; // * f(0) = 0 if (n == 1) return 1; // * f(1) = 1 table[n] = f(n - 1) + f(n - 2); // * f(n) = f(n - 1) + f(n - 2) return table[n]; } ``` --- ### 上課練習 [NEOJ #350 巴斯卡三角形]