Q1. 遞迴 (recursive) 是什麼?

• 遞迴是一種解題的方法，主要是透過「重複呼叫自身程式碼」，將大問題切成小問題來找到解答
• 提到 recursive(遞迴) 也需要順便介紹iterative(迭代)，迭代是利用迴圈(例如 for 或 while) 重複循環程式，來得到答案
• recursive(遞迴) 與 iterative(迭代) 時常一起被提起，因為通常可以利用遞迴/迭代實作的程式，往往也能使用另一種方法實作，所以面試程式題時，當你提出遞迴解時，面試官有時候也會要求你使用迭代的方式嘗試解答

Q2. recursive(遞迴) vs. iterative(迭代)

• 執行時間：
  • recursive(遞迴)：通常比較長，因為一直呼叫 function 和 return，會需要不斷傳遞參數，並且儲存與讀取 return 位置和保存暫存器狀態
  • iterative(迭代)：通常時間較短，不像遞迴需要儲存return，在 function 間一直跳轉
• 需要的空間：
  • recursive(遞迴)：呼叫 function 時，會將一些 function 資訊 push 到 call stack 中(這邊的 stack 是指記憶體中，專門存放 function 資料的區域，包含區域變數、參數、return 位址)，當呼叫太多次 function，導致 call stack 越來越滿，直到溢位，此時程式就會出現錯誤
  • iterative(迭代)：不會像遞迴一樣，讓 stack 快速成長
• 程式撰寫簡潔度：
  • recursive(遞迴)：在實作大多數比較複雜的演算法時(需要把大問題分成小問題)，程式可以較為簡潔，例如DFS、Quick Sort
  • iterative(迭代)：相比遞迴，在實作一些複雜演算法，程式更為繁瑣

Q3. 遞迴(recursive) 概念可以做什麼 ?

• 需要將大問題切分成小問題的題目，例如：
  • 前幾天實作的 Hoare Quick Sort
  • 實現 DFS
• 例如現在希望可以計算階乘，例如 3!，希望可以得到6
• 那麼此時可以使用 遞迴與迭代方式計算 (由於此題目較簡單，使用迭代會更好實作，在解決更複雜的問題時，遞迴會更好實作)

  • 遞迴：
    

  • 迭代：
    

Lab. 明天要解的題目：21. Merge Two Sorted Lists

題目連結：https://leetcode.com/problems/merge-two-sorted-lists/

題目敘述：

• 題目有兩個已經排序好的 linked list，你要將這兩個 linked list 合併成一個已排序過的 linked list
  

測資的 Input/Output：

• 會拿到兩個 linked list，需要合併後回傳
  

題目的條件：

• linked list 長度為 0~50

• linked list 的值為 -100~100

• 兩個 input 的 linked list 是遞增排序
  

• 看完題目，你要思考：

  • 如果你是使用 遞迴/迭代方式實作，那你是否也能用另外一種方式實作?