第 2 讲 · 程序设计、递归与调试

程序设计的难点不在于把语法写对，而在于把含糊的问题变成一组边界明确、能够验证的步骤。课件把“获得程序设计能力”的途径概括得很直接：读程序只能帮助理解，真正的能力来自自己分析、实现和调试。

先分清程序设计与程序设计语言

程序设计回答“怎样解决问题”；C 语言只是表达这个方案的工具。一个好的方案应先写清：

  • 输入是什么，范围和格式是什么；
  • 输出是什么，是否有唯一结果；
  • 核心数据需要怎样组织；
  • 处理可以拆成哪些彼此独立的步骤；
  • 哪些边界情况最容易出错。

直接把整道题塞进 main 往往会同时混合输入、数据组织、算法和输出。一旦出错，很难确定是哪一层出了问题。

模块化：每个函数只负责一件事

函数的接口由参数、返回值和副作用组成。设计函数时，应让调用者不必知道内部细节。例如链表问题可以拆成：创建结点、查找位置、插入、删除、打印和释放。

好的函数还应明确所有权：谁申请内存、谁最终释放；传入的是值、地址，还是可能被修改的结构。

递归为什么有效

递归把一个问题写成“同类但规模更小的问题”。完整递归必须有：

  1. 基本情况：直接得到答案并停止继续调用；
  2. 递归情况：把当前问题缩小；
  3. 组合方式：利用子问题答案得到当前答案。

阶乘可以写成

n!={1,n≤1,n(n−1)!,n>1.n!=\begin{cases} 1,&n\le 1,\\ n(n-1)!,&n>1. \end{cases} 
long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

每次调用都把 n 减一，因此一定走向基本情况。

调用栈里发生了什么

每次函数调用都要保存参数、局部变量和返回位置。递归深入时，这些现场按后进先出的顺序压入调用栈；到达基本情况后，再逐层返回。

因此递归写法短，不表示执行代价小。递归深度为 hh 时，调用栈通常至少需要 O(h)O(h) 空间。没有终止条件或规模没有缩小，会不断压栈并最终溢出。

汉诺塔体现的分解方式

把 nn 个盘从 A 移到 C：

  1. 先把上面 n−1n-1 个从 A 移到 B；
  2. 把最大的盘从 A 移到 C；
  3. 再把 n−1n-1 个从 B 移到 C。

移动次数满足 T(n)=2T(n−1)+1=2n−1T(n)=2T(n-1)+1=2^n-1。递归结构很自然，但复杂度也说明规模稍大就不可行。

调试不是反复改到“能跑”

源课件以 Dev-C++ 演示断点、单步执行和变量观察。工具可能变化，方法不变：

  1. 用最小输入稳定复现问题；
  2. 先写出这个输入下的预期状态序列；
  3. 在关键状态变化前设断点；
  4. 单步执行，观察变量、数组、指针和调用栈；
  5. 找到“第一次偏离预期”的语句。

最终输出不对只是结果，第一次错误状态才接近原因。

三类常见运行错误

SIGSEGV

通常来自非法内存访问：野指针、空指针解引用、数组越界、已经释放的内存再次使用。先检查指针是否初始化，再检查下标范围和生命周期。

SIGFPE

常见原因是整数除零或取模时除数为零。不要只检查字面量，也要检查经过计算后可能变成零的变量。

SIGABRT

常见于重复释放、释放错误地址、堆越界破坏了分配器维护的信息。问题往往发生在报错之前，因此要向前追踪最近的内存写操作。

一套可复用的自测方式

至少准备：

  • 最小合法输入；
  • 空输入或零元素；
  • 单元素；
  • 恰好触及容量边界；
  • 重复元素；
  • 已有序和完全逆序；
  • 不存在目标的查找；
  • 会改变头、尾或根结点的操作。

能解释这些输入下每一步的结构状态，才算真正掌握了程序。

评论