4.1. 使用辅助函数编写 reverse 和 split 函数¶

你会如何设计一个 reverse 函数，它接受一个整数列表，并返回一个包含与输入列表相同元素、但顺序相反的列表？

> reverse( [1,2,3] )   // we could start with [ ] and insert 1 into it to get [ 1 ]
[ 3, 2, 1 ]            // then insert 2 into [ 1 ] to get [ 2, 1 ]
                       // then insert 3 into [ 2, 1 ] to get [ 3, 2, 1 ]
> reverse( [ ] )
[ ]

使用 累加器模式 的要点是，为我们正在编写的函数添加一个额外的实参，称为 累加器 ，并把它加到该函数的辅助函数上。对于 reverse ，我们可以使用一个递归的辅助函数，它接受输入列表 ns 和正在构建的列表 acc 。下面的幻灯片对此进行了说明。

Settings

Saving...
Server Error
Resubmit

作为使用累加器的另一个例子，考虑你会如何设计一个 split 函数，它接受一个整数 \(n\) 和一个整数列表 \(ns\)，返回两个列表，其中第一个包含 \(ns\) 中所有小于 \(n\) 的元素，第二个包含 \(ns\) 中剩余的元素？

> split(5, [1,9,2,8,3,7])
[ [ 3, 2, 1 ], [ 7, 8, 9 ] ]
> split(5,[ ])
[ [ ], [ ] ]

我们把 split 的第一个实参称为 枢轴 ，因为有一个著名的算法用到了 split（见下面第二道复习题）。

Settings

Saving...
Server Error
Resubmit

第一道复习题将测试你对 split 以及另一个名为 join 的函数的理解，后者也是用累加器编写的。

4.2. 使用 split 函数编写排序函数¶

这道题将让你使用 split 函数来实现一个高效的排序算法。

4.3. 累加器模式的更多练习¶

这道题将让你对累加器模式进行更多练习。它是一道随机化习题。你必须连续三次答对。