【第十二天 - 递回介绍】

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 是递增排序
  

• 看完题目，你要思考：

  • 如果你是使用 递回/迭代方式实作，那你是否也能用另外一种方式实作?