Ouch. I tried to figure out the Towers of Hanoi last year. The tricky thing about TOH is it's not a simple example of recursion - you have nested recursions which also change the roles of towers on each call. The only way I could get it to make sense was to literally visualize the movement of the rings in my mind's eye, and verbalize what the recursive call would be. I would start with a single ring, then two, then three. I actually ordered the game on the internet. It took me maybe two or three days of cracking my brains to get it.

Common Lisp中的简单递归示例:

MYMAP对列表中的每个元素应用一个函数。

1)空列表没有元素，所以我们返回空列表-()和NIL都是空列表。

2)将函数应用到第一个列表，对列表的其余部分调用MYMAP(递归调用)，并将两个结果合并到一个新列表中。

(DEFUN MYMAP (FUNCTION LIST)
  (IF (NULL LIST)
      ()
      (CONS (FUNCALL FUNCTION (FIRST LIST))
            (MYMAP FUNCTION (REST LIST)))))

让我们观察跟踪执行。在输入函数时，输出参数。在退出函数时，输出结果。对于每个递归调用，输出将按级别缩进。

这个例子对列表(1 2 3 4)中的每个数字调用SIN函数。

Command: (mymap 'sin '(1 2 3 4))

1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
|   3 Enter MYMAP SIN (3 4)
|   | 4 Enter MYMAP SIN (4)
|   |   5 Enter MYMAP SIN NIL
|   |   5 Exit MYMAP NIL
|   | 4 Exit MYMAP (-0.75680256)
|   3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)

这是我们的结果:

(0.841471 0.9092975 0.14112002 -0.75680256)

如果你想要一本很好地用简单的术语解释递归的书，可以看看Gödel，埃舍尔·巴赫:道格拉斯·霍夫施塔特的《永恒的金辫子》，特别是第五章。除了递归，它还能很好地以一种可理解的方式解释计算机科学和数学中的许多复杂概念，一个解释建立在另一个解释的基础上。如果你以前没有接触过这类概念，这可能是一本非常令人兴奋的书。

你的大脑爆炸是因为它进入了无限递归。这是初学者常犯的错误。

信不信由你，你已经理解了递归，你只是被一个常见的，但错误的函数比喻拖了下来:一个小盒子，里面有东西进进出出。

而不是考虑一个任务或过程，比如“在网上找到更多关于递归的知识”。这是递归的，没有问题。要完成这个任务，你可以:

a) Read a Google's result page for "recursion"
b) Once you've read it, follow the first link on it and...
a.1)Read that new page about recursion 
b.1)Once you've read it, follow the first link on it and...
a.2)Read that new page about recursion 
b.2)Once you've read it, follow the first link on it and...

如您所见，您已经做了很长一段时间的递归工作，没有出现任何问题。

你会坚持做这个任务多久?永远，直到你的大脑爆炸?当然不是，只要你相信你已经完成了任务，你就会停在一个给定的点上。

当要求你“在网上找到更多关于递归的知识”时，没有必要指定这一点，因为你是一个人，你可以自己推断。

计算机无法推断任何东西，所以你必须包含一个明确的结尾:“在网上找到更多关于递归的知识，直到你理解它或你阅读了最多10页”。

您还推断应该从谷歌的结果页面开始进行“递归”，这也是计算机无法做到的。递归任务的完整描述还必须包括一个显式的起点:

“在网上找到更多关于递归的知识，直到你理解它，或者你已经阅读了最多10页，并从www.google.com/search?q=recursion开始”

要想全面了解，我建议你试试下面这些书:

普通Lisp:符号计算的简单介绍。这是对递归最可爱的非数学解释。 小阴谋家。

你在用哪本书?

关于算法的标准教科书是Cormen & Rivest。我的经验是，它很好地教授了递归。

递归是编程中较难掌握的部分之一，虽然它确实需要本能，但它是可以学习的。但它确实需要一个好的描述，好的例子和好的插图。

此外，30页通常是很多的，30页是用一种编程语言编写的。在你从一本普通的书中理解递归之前，不要尝试用C或Java学习递归。

要向一个六岁的孩子解释递归，首先要向一个五岁的孩子解释，然后再等一年。

实际上，这是一个有用的反例，因为递归调用应该更简单，而不是更难。向一个5岁的孩子解释递归就更难了，尽管你可以在0点停止递归，但你没有简单的解决方案来向一个0岁的孩子解释递归。

要使用递归解决一个问题，首先将其细分为一个或多个可以用相同方法解决的更简单的问题，然后当问题简单到无需进一步递归就可以解决时，您可以返回到更高的级别。

事实上，这是用递归方法来解决问题的递归定义。