# RECURSION 「遞迴」 --- # 概念  [^1] --- ## 大綱 * 概念 * 應用 * 例子 * 疑問 * 討論 --- ## 應用上:LOOP for loop while loop do while loop --- ## For loop ```java= for(條件式){ } ``` --- ## While loop ```java= while(條件式){ } ``` --- ## do while loop ```java= do { } while (條件式 ); ``` --- ## 主要概念: 遞迴:將問題分解為更小的問題 --- ## 古代文學上 回文: 暖風吹冷水 --- # 生活上例子: 貸款 複利 定存 --- # 生活上例子:  --- # 生活上例子: 買珍珠奶茶的例子， 我們來看看真實生活的行為如何對應到遞迴的形式 ``` 條件： 問到目前正在點餐的客人為止 步驟： 不斷地詢問前一位等待的人是第幾位是遞迴步驟 ``` [^2] --- # 疑問? 遞迴跟迭代差在哪裡? ---  [^3] --- # 定義 在電腦科學中 是指一種通過重複將問題分解為同類的子問題而解決問題的方法。 資料的結構形式是按遞迴定義的。如二元樹、廣義表等 --- # 常見的範例1 加總 ```java= int sum(int n) { int i; // 紀錄目前要處理的數字 int sum = 0;// 紀錄到目前為止的總和 for (i = 1; i <= n; i++) { sum = sum + i; } return sum; } ``` --- # 遞迴 加總 ```java= public static int getTotal(int number) { //檢查是否為0 if (number != 0) { //遞迴 return number + getTotal(number - 1); } //當number=0時跳出 else { return number; } } ``` --- # 常見的範例2 最大公因數 (GCD) -整除多個整數的最大正整數。 而多個整數不能都為零 ```java= int gcd(int x, int y) { int tmp; // 如果x < y 則下面的迴圈執行第一次時就會交換x,y了 while (x % y != 0) { tmp = y; y = x % y; x = tmp; } return y; } ``` --- # 遞迴 輾轉相除法 ```java= class Test{ // 遞迴算出a、b的GCD static int gcd(int a, int b){ // 檢查a、b是否為0 if (a == 0){ return b; } if (b == 0){ return a; } // 檢查a、b是否相等 if (a == b){ return a; } // a 較大 if (a > b){ return gcd(a-b, b); } return gcd(a, b-a); } public static void main(String[] args){ int a = 98, b = 56; System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b)); } } ``` [^4] --- # 常見的範例3 費波納契數列 (FIBONACCI SEQUENCE) 圖片:  --- # 費波納契數列 ``` -第一個月初有一對剛誕生的兔子 -第二個月之後（第三個月初）牠們可以生育 -每月每對可生育的兔子會誕生下一對新兔子 -兔子永不死去 ``` [^5] --- # 算法 ```java= F1=1 F2=1 Fn = Fn–1 + Fn–2 (n ≧ 2) ``` --- # 常見的範例4 N 個字元的排列組合 a、b、c --- # 常見的範例5 TOWERS OF HANOI  [^6] --- # 演算教學 {%youtube YstLjLCGmgg %} --- # 問題1 LeetCode 21. Merge Two Sorted Lists  --- # 前題 ``` Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4] The number of nodes in both lists is in the range [0, 50]. -100 <= Node.val <= 100 Both list1 and list2 are sorted in non-decreasing order. ``` --- # java解答 ```java= /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null) { return l2; } if(l2 == null) { return l1; } if(l1.val < l2.val){ l1.next = mergeTwoLists(l1.next, l2); return l1; }else{ l2.next = mergeTwoLists(l1, l2.next); return l2; } } ``` --- # 問題2 LeetCode 203. Remove Linked List Elements  ```java= public ListNode removeElements(ListNode head, int val) { if (head == null) return null; head.next = removeElements(head.next, val); return head.val == val ? head.next : head; } ``` --- ### 河內塔網頁版 https://www.mathsisfun.com/games/towerofhanoi.html --- ### 參考網頁 [^7] --- <!-- .slide: data-background="http://i.giphy.com/90F8aUepslB84.gif" --> ## ... and thx for listening! [^1]:[ref1](https://www.csie.ntu.edu.tw/~kmchao/c04fall/Chapter10.ppt) [^2]:[ref2](https://ithelp.ithome.com.tw/m/articles/10265916) [^3]:[ref3](https://www.geeksforgeeks.org/difference-between-recursion-and-iteration/) [^4]:[ref4](https://www.geeksforgeeks.org/c-program-find-gcd-hcf-two-numbers/) [^5]:[ref5](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0) [^6]:[ref6](https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/) [^7]:[ref7](https://hackmd.io/slide-example?both)