2.1 作為遞歸 ADT 的 list

List 是課程第一次把 recursion 變成資料結構本身的語言，而不只是程式技巧。 List 不是單純用括號畫出來的 array；它有一個契約：要麼是 empty list，要麼 由一個 head element 和一個本身仍然是 list 的 tail 組成。

這個遞歸定義解釋了為甚麼 list 程式常常有同一個形狀：先處理 empty list， 再處理 head，然後把剩下的工作交給 tail。

List 契約

Lecture 先強調三個操作：

• CreateList(head, tail)：由一個元素和一個 list 建立新 list；
• ListHead(list)：取第一個元素；
• ListTail(list)：取去掉第一個元素後剩下的 list。

Head 和 tail 的類型不同。Head 是元素；tail 是 list。例如 $L = [3, 6, 4, -3, 0]$ 時，$ListHead(L) = 3$，但 $ListTail(L) = [6, 4, -3, 0]$。

CreateList(3, CreateList(4, CreateList(5, EmptyList())))

為甚麼 recursion 自然適合 list

List 的遞歸結構直接給出很多 function 的寫法。

int ListLength(listADT list) {
   if (ListIsEmpty(list)) {
      return 0;
   }
   return 1 + ListLength(ListTail(list));
}

End case 是 empty list。Recursive call 是對 tail 做，而 tail 比原本 list 短。如果沒有 end case，或者 recursive call 沒有令問題變小，遞歸就不安全。

同樣，NthElement 的思路是：第 0 個元素是 head；第 n 個元素是 tail 的第 $n-1$ 個元素。

Iteration 和 recursion 只是保存狀態的方法不同

Iterative ListLength 會用 cursor 逐步走過 successive tails。

int ListLength(listADT list) {
   int count = 0;
   for (listADT L = list; !ListIsEmpty(L); L = ListTail(L)) {
      count++;
   }
   return count;
}

Recursive 版本把未完成工作放在 call stack；iterative 版本把它放在 local variables。兩者正確，都是因為每一步都從 current list 走向 tail。

Representation 會改變成本

Array-based list 可以實作同一個 ADT，但 CreateList 可能要把 tail 的所有 元素複製到新 array。Linked representation 則儲存一個 head 和一個指向 tail 的 pointer，因此 CreateList 可以只 allocate 一個新 cell，再指向原本 的 tail。

ADT 告訴我們操作的意思；representation 決定操作的成本。

常見錯誤

• 把 ListTail(L) 當成元素，而不是 list。
• 未處理 empty list 就呼叫 ListHead。
• 假設 array representation 和 linked representation 成本一樣。
• Recursive call 仍然用原本 list，沒有把問題縮小。

練習

1. 說明 DisplayList 的 recursive idea：print head，再 display tail。
2. 解釋為甚麼 ListConcat(list1, list2) 在 list1 empty 時應該 return list2。
3. 比較 array representation 和 linked representation 下 CreateList 的成本。