第 1 课导言：函数式编程与递归

函数式编程

在本课中，我们将深入学习函数式编程（functional programming）和递归（recursion）。递归过程（recursive procedure）通过某种方式把大问题略微变小，然后调用自身来求解。而当它调用自身时，问题又变小了一些。这个过程持续进行，直到问题小到可以直接解决。

如果你以前从未用过递归，可能会觉得它不太容易上手。用递归编程时，请记住以下几点：

1. 一定要有基准情形（base case）。递归应该走到某一步，此时不再需要调用自身就能得到答案。到某个时候，问题应当简单到直接输出答案即可。
2. 始终让问题变小。每次进行递归调用时，都要确保实参比开始时更小。否则，你可能会陷入讨厌的无限循环。
3. 最后，相信递归！ 不要想太多。如果你的递归思路合理，并且你遵循了前两条准则，代码大概就能工作。你并不总是一步步追踪递归的执行过程，来确认过程是否如你所愿地工作。

先修要求与本课目标

学习本课前，你应当了解 Racket 的基础知识，并掌握正确的语法。

在本课中，你将学习递归。

阅读材料

本课的相关阅读材料如下：

• SICP 1.1 - The Elements of Programming
• 课堂笔记

如果你想找更多资料，可以查看 Unit 0 的全部阅读材料。

函数

在讨论计算机科学中的函数之前，我们先来说说数学中的函数。在数学里，函数 $f(x)$ 接受单个输入 $x$，对它”做点什么”，然后返回一个新值。对于函数接受的每一个 $x$，它只返回一个值，而且每次都返回相同的值。例如，如果 $f(x) = x + 2$，那么每次把 4 代入 $f(x)$，我们都会得到 6。绝不会有输入 4 却得到 5、7 或其他值的情况。

计算机科学中也是如此！函数（function）被定义为一种过程（procedure），其特点是输出取决于输入——也就是说，给定某个（或某些）输入时，它每次都返回相同的输出。

(define (square x)
  (* x x))

这是一个函数，因为无论输入什么，我们总能得到该输入乘以它自身的结果。

除了函数之外，Racket 还有一种更通用的数据类型，称为过程（procedure）。过程与函数类似，但它不一定要对每个输入都返回相同的输出。例如，square 是函数，而 random 不是，因为对于相同的输入，每次调用 random 都可能得到不同的输出。

需要澄清的是：在 Racket 中，所有函数都是过程，但并非所有过程都是函数。

本小节涵盖的内容有：

1. 函数——它们是什么，如何定义它们。
2. 基本过程（primitive procedures）
3. 特殊形式（special forms）

接下来做什么？

开始下一小节 1 吧！