CS61A 学习笔记：抽象、函数与递归

CS61A 的重点并不只是 Python 语法，而是如何用抽象控制复杂度。课程从函数开始，逐步进入递归、数据抽象、面向对象、解释器与声明式编程。

高阶函数

当函数可以作为参数传入、也可以作为结果返回时，很多相似的控制流程可以被抽象出来。

def improve(update, close, guess=1):
    while not close(guess):
        guess = update(guess)
    return guess

improve 不关心具体求什么，只描述“不断更新直到足够接近”的过程。牛顿法、黄金分割等不同算法，可以通过传入不同函数复用同一结构。

递归的三个检查点

写递归函数时，我会依次检查：

1. 基线条件能否直接给出答案；
2. 递归调用是否真的让问题规模变小；
3. 当前层如何利用子问题的结果构造最终答案。

例如计算树中叶子节点的数量，当前节点只需要把各个分支的结果相加，不必了解子树内部如何遍历。

数据抽象

数据抽象通过构造器和选择器隔离“数据如何表示”与“数据如何使用”。只要接口不变，内部表示就可以替换。这个思想会在类、模块、数据库和服务接口中反复出现。

学习体会

这门课程最值得反复练习的是环境图与递归。环境图帮助解释闭包、局部状态与名称查找；递归则训练把大问题拆成结构相同的小问题。把每道题的调用过程画出来，通常比盯着代码更快发现错误。