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 的成本。