什么是递归

递归（recursion）是一种编写过程的方法，用来解决某类问题。这类问题的解法依赖于同一问题更小实例的解法。通常，递归会让我们一次又一次地重复同一个过程。它看起来有点像这样：

递归过程的奇特之处在于：为了调用这个过程，我们需要让这个过程调用它自己，而这个调用又得调用它自己，如此继续——我们还是盯着一个例子看吧。

例子：阶乘

在数学中，非负整数 n 的阶乘记作 n!，是所有小于等于 n 的正整数的乘积。例如，3! = 3 * 2 * 1。此外，根据定义，0! = 1。

怎么用 Racket 写出 factorial 过程呢？这是个挑战，因为我们要相乘的数取决于我们要求阶乘的那个数，也就是实参。

因此，我们要用到递归。我们把它分成两种情况：

• 如果 n ≥ 1，那么 n! = n * (n-1)!
• 如果 n = 0，那么 n! = 1

递归严重依赖条件表达式。如果已经算完了，就返回某个值；否则，继续递归。以阶乘为例，我们一路递归直到 n = 0，然后返回 1。据此可以写出 factorial。看看下面 Racket 版的 factorial 解法，看能不能看懂。也在解释器里试试吧！如果暂时看不懂代码也没关系。下一小节我们会更明确地讲解递归。

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

要点总结

本小节的内容包括：

1. 什么是递归？
2. 如何用递归定义阶乘？

进入下一小节，学习递归是如何工作的。