CHAPTER 2
第2章 递归

GNU=GNU'S Not Unix

——理查德·斯托曼对开源软件操作系统的命名

人们探索数进而探索自然。在上一章中，我们介绍了自然数的皮亚诺公理系统，并且展示了和自然数“同构”的事物，例如“列表”数据结构。自然数是前进的基石，但是我们的大厦还不稳固。在第1章中，我们不加证明地使用了递归的概念，例如阶乘的定义：

fact(0)=1

fact(n+1)=(n+1)fact(n)

递归的原理是什么？为什么它是正确的？递归可以在更基础的层次被表示么？本章我们讨论这些有趣的问题。