跳至内容
Topos Uranos
中文 (中国)

函数：总结与挑战

摘要

本课结束本课程的第五单元，这一单元专讲函数。本课重建从函数的声明通向递归的概念链，途经调用栈、契约、参数的传递、变量的作用域与生存期，以及逐步求精的设计；把其中适用于任何语言的内容与 C++ 特有的内容区分开；汇总本单元的未定义行为，连同编译器会警告什么、检测器会拦下什么、以及什么谁也不会指出；在结业测评中重复入门测评的各项技能；最后给出六道综合整个单元的挑战题。

学习目标

  1. 把一个问题分解为若干函数，每个函数都有自己的接口和契约（前置条件和后置条件），并分别测试它们。
  2. 为每个参数选择传递方式，选择返回结果的方式，并说明选择的理由。
  3. 用递归解决问题，用归纳法证明其正确性，用一个递减的度量证明其终止，并估计其以调用次数计的代价。
  4. 识别本单元的未定义行为（没有 return 的路径、悬垂引用、溢出的结果、耗尽的栈），并把程序改写得没有它。
  5. 在本单元所学的内容中，区分适用于任何语言的内容与 C++ 特有的内容。

本单元的收获

本单元的目标是教会把一个问题分解为有名字的部分，每一部分都有接口和契约，并用递归解决问题。这一目标已经达成，所依靠的只是导言声明为已知的内容：第 4 单元的循环及其不变式和变式、第 1.1 课的规格说明，以及第 2 单元的内存模型。亲和数的程序曾因复制的循环把错误的数的因数相加起来，现在只用一个函数来写，这个函数只需对照其契约验证一次。

函数

函数一课教了如何声明、定义和调用函数，并区分了三个时刻：编译时，每次调用都对照此前见过的声明进行检查；链接时，查找定义；运行时，先计算实参，再在调用栈上创建一个栈帧，然后控制转入函数体。它说明了，一个不是 void 的函数在没有 return 的情况下到达末尾是未定义行为，最后讲了契约，即前置条件和后置条件，它在调用者与函数之间分配责任。

参数与作用域

参数与作用域一课研究了数据经由哪些途径进入、结果经由哪些途径离开：按值传递的形参是一份副本；按引用传递的形参是调用者那个存储单元的第二个名字；常量引用只读而不复制。由此得出选择的规则（小的用值，只读的大对象用常量引用，只有修改本身就是目的时才用引用），以及对于多个结果，用 std::pair 和 std::tuple 配合结构化绑定。它区分了名字的作用域（文本的性质）和变量的生存期（执行的性质），最后讲了比自己的存储单元活得更久的引用。

用函数进行设计

用函数进行设计一课教了如何用逐步求精来决定要写哪些函数：一个简短的 main 调用只声明过的函数，再逐一深入每个函数，于是分解可以画成一棵树。它确立了好接口的标准和“一个函数，一项任务”的规则，以及这一规则的迹象（名字里的连词、一屏放不下的函数、标志变量）和隐藏的作用，例如全局变量；介绍了重载及其优先顺序和有歧义的调用；并把第 4 单元的算法改写成分别测试过的函数。

递归

递归一课讲了函数可以调用自身，以求解问题的一个更小的实例。它用归纳法证明了正确性（假定更小的调用是正确的），用一个递减的自然数度量证明了终止；借助栈跟踪了压入又弹出的栈帧，并说明了栈如何耗尽；提醒结果的类型远在栈耗尽之前就会溢出；并比较了斐波那契数的递归版本与迭代版本：2 692 5372\,692\,537 次调用对 29 次加法（求 F30F_{30}）。