iT邦幫忙

2021 iThome 鐵人賽

DAY 12
1
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 12

【第十二天 - 遞迴介紹】

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
  • 那麼此時可以使用 遞迴與迭代方式計算 (由於此題目較簡單,使用迭代會更好實作,在解決更複雜的問題時,遞迴會更好實作)
    • 遞迴:
      https://ithelp.ithome.com.tw/upload/images/20210912/20140592t3UfYnuq3v.png

    • 迭代:
      https://ithelp.ithome.com.tw/upload/images/20210912/20140592nLh4xsvbpi.png

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

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

題目敘述:

  • 題目有兩個已經排序好的 linked list,你要將這兩個 linked list 合併成一個已排序過的 linked list
    https://ithelp.ithome.com.tw/upload/images/20210912/20140592Kbsmdp7K4C.png

測資的 Input/Output:

  • 會拿到兩個 linked list,需要合併後回傳
    https://ithelp.ithome.com.tw/upload/images/20210912/20140592f2Tn3kirbA.png

題目的條件:

  • linked list 長度為 0~50

  • linked list 的值為 -100~100

  • 兩個 input 的 linked list 是遞增排序
    https://ithelp.ithome.com.tw/upload/images/20210912/20140592i01D5IQM7t.png

  • 看完題目,你要思考:

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

上一篇
【第十一天 - Two-pointer 題目分析】
下一篇
【第十三天 - 遞迴 題目分析】
系列文
【帶你輕鬆入門演算法-Leetcode】30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言