第八章 递归（recursion）
8.1 导语
因为一些指导者倾向于先教递归作为第一个主要的控制结构，本章会以另一种方式继续教学，他们是互相独立的。
在计算机科学中，递归是一个最基础而美妙的概念。如果一个函数调用自身的话，我们就成这个函数是递归的。递归控制结构是本章的主要话题，但是我们也会在进阶话题中了解递归数据结构。想要分辨很多问题的递归本质，你需要多多的开发练习，直到你掌握为止。你可能会惊讶的发现三四行递归程序就能做到的事。
我们会用三种技术互相结合来体现什么是递归：龙的故事。程序追踪和递归模板。龙的故事部分是最有争议的，学生们细化并且认为他很有用，但是计算机专家学者们则很不感冒。如果你不喜欢龙的故事没那么可以跳过相关小节、其间的部分也会很好的表达意思，只是少了很多生趣。
8.2马丁和龙
在很久之前的远古时代，在计算机被发明之前，炼金术师很学到了关于数字的神秘属性。没有计算机，他们只能借助龙的力量来为他们工作。龙是具有非凡智慧的生物，但是也很懒惰，脾气也很坏。最糟糕的一点是有时候会用致命热度的吐息把他的饲主烤的外焦里嫩，但大部分龙仅仅是不想合作而已，没有那么暴力。这个故事关于马丁，一个炼金术师学徒，通过一个超级聪明的懒龙发现递归的故事。
有一天师傅给了马丁一个数字的列表，让他去地牢里面问问龙，哪一些数字是奇数，马丁之前总来没有去过地牢。他拿上了蜡烛，在地牢欧洲的最最深处的阴暗角落，发现了一只老龙，看上去并不是很友好的样子。马丁一步步的缓缓前进，他很害怕，他可不想被烤的外焦里嫩。
“你要做什么？”龙疑心重重地看着马丁，带着愠怒嘀咕。
“请帮助我，龙，我有一个数字的列表，需要知道哪些数字是奇数。”马丁开始请求“请看”，他在布满灰尘的地上，用手指写下了师父给的数字列表。
(3142 5798 6550 8914)
那条龙那天心情不是很好，其实作为一条龙，哪天心情都不好。“对不起了”龙说“我能做的顶多就是告诉你第一个数字是不是奇数，其他的太麻烦了，别来打扰我”。
“但是我必须要知道列表里的所有数字是不是奇数呀，不只是第一个数字”马丁解释道。
“那真的是对不起了”龙说“我只看列表的第一个数字，但是你把数字一个个给我看的话或许就能如愿以偿了。”
马丁想了一想，现在也只好听龙的指示来做了“那第一个数字是不是奇数呀？”他问。
“第一个数字不是奇数”，龙回答。
马丁用手遮住了列表的第一个元素，然后添上一个左括号。
(5798 6550 8914)
然后又说：“那这个列表呢？”
“第一个元素不是奇数”龙回答说。马丁然后又遮住更多元素“那现在这个呢？”
(6550 8914)
“第一个元素也不是奇数”龙说，然后环顾了一下四周，看上去很不耐烦，但至少还是比较合作的。
“那还有这个呢？”马丁追问。
(8914)
“不是奇数”
“那这个呢？”
()
“那是一个空列表！”龙哼了一声。“他不可能是一个奇数，因为它里面什么都没有！”
“非常好”马丁说，“我现在已经知道了列表里没有数字是奇数，师傅给我的数字都是偶数。”
“我从没这样说过！”龙咆哮着怒吼。马丁已经问到了火药味了“我只是告诉你你给我看的每一个列表的第一个数字是不是奇数！”。
“确实如此，龙。那我写下给你看的所有列表还不好。”
“如果你想的话”，龙很傲娇的回答。马丁开始在地上写：
(3142 5798 6550 8914)
(5798 6550 8914)
(6550 8914)
(8914)
()
“你现在看到了吗？”马丁问“通过告诉我每一个列表的第一个元素不是奇数，你已经告诉我原来的列列表没有奇数了。”
“这是个鬼把戏”，龙暴躁的说，“看上去你已经发现了递归了，但是你别问我递归是什么意思，你必须自己去找到他的意义。”龙闭上眼睛一言不发的休息去了。
8.3 一个搜索奇数的函数
这里有一个递归函数anyoddp，如果有任何元素师奇数，就返回T。列表中没有奇数的话就返回nil。
如果列表是空的，那么anyoddp就会返回nil，正如龙所说，一个不包含任何东西的类表不会是一个奇数。如果一个列表不为空，我们会进入第二个cond语句，然后测试第一个元素。加入第一个元素师奇数，那么就没有必要再看下去了，可以停止并且返回T了。当地一个元素师偶数，anyoddp就会调用自身来继续处理列表其余的部分。这就是定义的递归部分。
为了根号的理解anyoddp是如何工作的，我们可以使用dtrace来显示每一个函数调用和每一个返回值。这个dtrace工具在第七章介绍过了，如果你的lisp没有dtrace的话，可以使用trace代替。
我们一开始会使用一个最简单的列表：一个空列表，还有一个奇数的列表。
现在请你考虑一个列表中出现偶数的情况，在第一个两个cond语句哪里会是一个false，所以函数会由第三个语句来结束，他会递归调用anyoddp自身来处理列表的剩下的元素。如果rest是nil的话，那么第一个语句就解决问题了，返回nil。
如果这个列表包含两个元素，一个偶数和一个奇数，递归调用将会除法第二个cond语句而不是第一个。
最后，我们来考虑一般情况下，奇数和偶数并存的情况。
请注意在上述函数的例子中没有不得不递归到nil的情况，既然列表（7 8 9）的first是奇数，那么anyoddp就可以停止在那个点上并且返回T。
8.4 马丁的再访
“你好！龙先生！”马丁从快散架的地牢楼梯上走下来的时候说。
“恩！？又是你！我已经中了你的递归圈套了！”龙嫌弃地看着他。
“我想找到5的阶乘是什么。”马丁说“首先，到底阶乘是什么意思呀？”
龙正在气头上，“我是不会告诉你的，自己去看书吧”。
“好吧”马丁说“只要告诉我5的阶乘是什么，我马上就走！”。
“”你连阶乘是什么意思都不知道来来问我5的阶乘是什么？好吧混蛋，我告诉你，但是没那么容易。5的阶乘就是4的阶乘的5倍，走的时候把门带上，不谢。“
“但是4的阶乘是什么呢？”，马丁问，看上去对龙的含糊其辞很是不满意。
“4的阶乘？那当然是3的阶乘的4倍了”
“看样子你要准备告诉我3的阶乘是2的3倍了”马丁说。
“你那么聪明别来找我呀”龙说“现在滚出去！”。
“还没完呢！”马丁回答。“2的阶乘是1的两倍，那1的阶乘是0的1倍，是吧？”
“0的阶乘是1”龙说“这个是你真的要记住的阶乘。”。
“姆。。。这个阶乘函数有一个模式，也许我应该将步骤写下来。”
“好的”龙说“你可以将所有阶乘都递归为0的阶乘，也就是1 。 现在你可以尝试在一步步退回。。。”龙话说到一半停住了，他不想表现的乐于助人的样子。
马丁又开始写：
“hey！”马丁尖叫道，“5的阶乘是120，就是答案了，谢谢！”。
“我没有告诉你答案！”龙暴怒，“我只是告诉你0的阶乘是1，n的阶乘解释n倍的n-1的阶乘而已，你给自己的应用了rest，递归的。”。
“确实如此”马丁说“现在我明白递归的真正含义了。”。
8.5 一个lisp版本的factorial函数
龙的话给了我们一个阶乘函数factorial的定义：n的阶乘就是n倍的n-1的阶乘0的阶乘是1 。函数fact可以递归的计算阶乘：
下面是lisp如何解决马丁的问题的：
8.6 龙的梦
这一次马丁来到地牢里的时候，他发现龙在拼命眨眼，就好像刚刚从一个长梦中苏醒一样。
“我做了一个有趣的梦。”龙说，“实际上这是一个递归的梦，你想不想听听？”
马丁被龙有好的态度吓了一跳，网结论炼金术师师傅给的最新的问题，说“请说吧，说说你的梦”。
“很好”，龙开始说了，“昨天晚上我正在盯着一条很长的面包，想着他能够被切成多少片。于是我真的拿起了刀开始一片片的切起来。我有了一片，面包开始短了，但是始终没有答案，带着问题我渐渐入眠。”。
“这就是你梦的内容？”马丁说。
"是的，有趣的是，我梦到的是另一条龙在做梦切面包，就像我一样，除了面包变短了。我太想知道到底有多少片了，。但是同样的问题出现，他像我一样切面包，像我一样入睡。"
“所以你没有找到答案，”马丁失望地说，“你不知道面包有多长，你也不知道他的有多长，除了他的面包比你的短。”
“是的，但是这还没完。”龙说，“当龙在我的梦里面入睡，也开始做梦。他梦到一头龙正在切面包。而且这条龙想要知道这条面包有多少片，尝试这一片片切，但是也没有得到答案就睡着了。”
“梦中梦！”马丁尖叫道，“你让我的大脑一团浆糊是不是最后一条龙也是同样的一个梦？”
“是的而且他不是最后的那条龙。没一条龙都梦到一条龙，做着同样的事情，我正在为这个梦堆砌起一个栈。”
“那你怎么叫醒他们？”马丁问：
“好的”龙说，“事实上有一条龙到最后的面包变得短到没有了。你可以称它是一个空面包。龙就看到那个面包没有一片存在，所以知道答案是0，于是就没有入睡。”
“当龙知道前一头龙的面包没有的时候，那就知道了自己的面包师1片，也就醒了过来，所以当答案揭晓，龙就会醒来。”。
“还有，当龙梦到的那头龙醒来的时候，他也就知道自己的面包师两片既然知道是比他梦到的那头龙多一片，那也就自然醒过来了。”
“我明白了”马丁说，“他他是在自己梦到的龙的面包片数加上1，就得到了自己问题的答案，当你醒过来的时候，你的答案是多少？”
“27”龙说，“那是一个很长的梦。”。
8.7 数面包片数的递归函数
如果我们将一片面包展现为一个符号，一条面包就是一个符号的列表。纳闷问题就是一条面包有多少片就是一个列表由多少个元素的问题。很明显是LENGTH函数的工作，但是如果我们没有length的话我们任然可以递归地来数。
如果输入是空列表，那么长度就是0，所以count-slices会简单的返回0。
如果输入是列表（X），count-slices就会递归地调用自己，来一步步处理输入，然后在自己的额结果上加上1.
当输入是一个很长的列表，count-slices不得不进行更深的递归来得到空列表返回0，之后的每一个递归调用都是在街上加上1 。
8.8 递归的三个规则
龙，对马丁问题的讨厌其实是虚伪的矫饰，事实上还是很喜欢教他递归的。一天它决定去正式的解释一下递归的含义。龙告诉马丁要想旅行一样去着手解决每一个递归问题。如果遵从下面三个规则来解决递归问题，就总是能够成功完成旅程。龙这样解释着规则：
1.知道什么时候停止
2.决定如何进行下一步
3.将一个旅程破拆成和一个更加小的旅程的合体
我们来看看每一个规则被应用在我们写的lisp函数的情况，第一条，“知道什么时候停止”，他警告我们任何递归函数在进一步递归之前都必须检查这个旅程是不是结束了。一般来说这是第一个cond语句的工作。在anyoddp中，第一个语句就是检查输入是不是空列表，如果是函数就停止并返回nil。这个而结成函数fact，当输入检测到0的时候就停止。0的递归是1，还有正如龙所说，这就是要记住的唯一一个阶乘。剩下的都可以递归计算出来。在count-slices函数中，第一个cond语句检查是不是nil，”空面包“，如果输入是nil那么count-slices就会返回nil。再说一次，这是基于空面包没有元素，为0的现实基础上，所以就可以不在递归。
第二条规则，”决定如何进行下一步“，要求我们知道将问题破拆成小部分之后如何解决。在anyoddp中就是判断是横下的列表的first是不是一个奇数。如果如此我们就返回T。在阶乘函数中我们是用一个简单乘法，将n和n-1的阶乘相乘。在count-slices中这一步是+函数。每一片都是从面包上球下来的，我们在加上去就知道了面包的长度。
第三条，”将旅程破拆成一小步加上更小的旅程“，意味着要找到一个方法来递归调用自身然后变成更加小的一部分。anyoddp函数就是调用自身来处理猎豹的rest部分，一个比原列表更短的列表，来看是不是有任何奇数。阶乘函数递归计算n-1的阶乘，一个比n的阶乘更加简单的问题，最终我们将通过它来计算出n的阶乘。在count-slices中我们递归调用一个面包的rest，然后在一个个加上就好。
| 龙的三个递归函数 | ||||
|---|---|---|---|---|
| 函数 | 停止时的输入 | 返回值 | 进一步处理 | 问题的rest |
| ANYODDP | NIL | NIL | (ODDP (FIRST X)) | (ANYODDP (REST X)) |
| FACT | 0 | 1 | N ´ ... | (FACT (- N 1)) |
| COUNT-SLICES | NIL | 0 | 1 + ... | (COUNT-SLICES (REST LOAF)) |
8.9 马丁发现无尽递归
这一次马丁到地牢里的时候，带给了龙一个羊皮卷。“看那，龙"他说“肯定还有其他人是知道递归的，我在练技术师的图书馆里找到了这个。”。
龙猜疑地看着马丁展开羊皮卷，将烛台放在尾部来保持平整。“这个羊皮卷没有任何意义”，龙说，“另外，太写的括号太多了。”。
"是写的有些奇怪"马丁同意，“但是我觉得我发现了一个信息，这是一个计算斐波那契数列的算法。”
"我已经知道如何计算斐波那契数列了"龙说。
“哦？是嘛？怎么计算？”
"为什么告诉你？哼！"龙回答。
"我也知道你不会的"，马丁反击说,"但是这个羊皮卷告诉我了斐波那契的第n个数字就是n-1个和n-2的和，这是一个递归定义，我已经知道如何计算数列了。’’
“羊皮卷还说了什么？”,龙问。
“没有其他的了，还应该说什么？”
突然龙摆出了一副谄媚的腔调，马丁发现有些异样，“亲爱的孩子，你可不笨一帮我这个又穷又老的龙一个小小的忙？为我计算一个斐波那契数，一个很小的数就好。”。
“额。。。我正要上楼清扫魔药锅的说”马丁开始说，但是看到龙脸上悲伤地表情的时候，又说“如果是一个很小的数字，那还行吧”。
“你不会后悔的。”龙允诺，“告诉我，第四个斐波那契数是什么？”。
马丁开始遵循斐波那契算法，那地上写：
Fib(n) = Fib(n-1) + Fib(n-2)
然后开始计算第四个斐波那契数；
Fib(4) = Fib(3) + Fib(2)
Fib(3) = Fib(2) + Fib(1)
Fib(2) = Fib(1) + Fib(0)
Fib(1) = Fib(0) + Fib(-1)
Fib(0) = Fib(-1) + Fib(-2)
Fib(-1) = Fib(-2) + Fib(-3)
Fib(-2) = Fib(-3) + Fib(-4)
Fib(-3) = Fib(-4) + Fib(-5)
“算完了没？”，龙卖萌地问。
“还没有”，出了点小问题，“有些东西出错了，数字开始想负数无限增长了。”。
"好的，你快完成了没？"。
“他看上去是无穷无尽的”，马丁说，“这个递归将永远进行下去。”。
"哈哈哈，你看到了吧。你已经陷入了一个无限递归了！"。龙幸灾乐祸的看，“我早就看到了。”。
"那你怎么不跟我说一声？"马丁质问说。
龙做了一个鬼脸，然后哼了一声，蓝色的火焰在鼻孔里冒了一下。“你是不是要永远依靠龙来帮助你思考？一直让龙来解决递归？”。
马丁没有害怕，但是他退了几步让烟火散去一些，“好吧，那你是怎么这么快发现问题的，龙？”。
“基础！孩子，这个羊皮纸告诉你如何进行计算步骤，和如何将大的过程分解成小的，但是却没有提到什么时候停止，是因为这个。”，龙露出牙齿笑起来。
8.10 lisp中的无限递归
lisp函数能够可以无视龙的第一条规则来制造一些无限递归函数，我们知道计算这是不会停止的。这里是马丁的算法的lisp实现。
一般来说，一个好的程序员可以看一下函数就辨别出这个函数是不是无尽递归的，但是在一些情况下可能是很难决定的一件事。尝试追踪函数C，输入就用小的正数。
尝试使用其他1到10的数字来调用C。请注意在输入数字的大小和递归的规模上没有明显的额关系。数学家相信，任何正数的输入都会返回T，也就是说没有输入会引起无限递归。就是知名的克拉兹猜想。至今还没有解决的问题，所以我们也不能保证任何输入都会有T返回。
8.11 递归模板
大部分Lisp递归函数都符合一些模板。这些函数就是被递归函数模板所描述的，这些模板可以用一个填补空格形式来抓住函数的本质。你可以通过选择一个模板，并且在中间填补空格来创造一个函数，当然也是的，一旦你掌握了这个方法，你就可以使用模板分析现有的函数，只打他们是使用哪一种模式。
8.11.1 双测试尾递归（double-test tail recursion）
我们要学习的第一个模板是双测试尾递归模板，如图8-1所示。“双测试”的意思是递归函数有两个测试结束部分，如果其中一个是真的话，那么对应部分的值就会被返回，不会再继续进行递归了。当两个端测试都是false，那么就结束在最后一个cond语句，这个函数接受输入，然后进行递归调用。这个模板被称为尾递归是因为他的最后一个cond语句出克递归之外不做其他的事情。无论递归产生什么结果，anyoddp是一个尾递归的例子。
8.11.2 单测试尾递归（single-test tail recursion）
单测试尾递归的是一个更简单的模板，但是使用没有那么频繁。假设我们想要找到一个列表的第一个元字符，可能这个元字符是隐藏在很深的嵌套结构中，我们可以一直使用first，知道找到那个元字符为止。这既是find-first-atom函数的作用。
一般来说，单测试递归的使用情况是在我们知道函数总是可以找到元素的。find-first-atom函数因为不断地使用first，所以肯定可以找到第一个元字符。在anyoddp函数中，例如，第二个测试检查是不是找到了一个奇数，但是第一个测试是检查列表是不是已经到了最后空的状态，那时候就应该返回nil.
8.11.3 增强型递归
增强型递归函数，像count-slices会一位一位的建立他们的结果。我们称这个过程是增强。不是吧一个问题分解成一个厨师步骤然后增加到更小一点的问题上，与这个策略不同，他们的策略就是分割成一个更小的部分然后加成一个最终结果。最终的一部是由一个增强型的值和应用到之前递归调用的结果来组成的。在count-slices中，例如，我们首先做一个递归调用然后给结果加上1来得到结果。
在尾递归函数中，结果没有任何增强也是可以的。因此，尾递归返回的值总是等于函数定义中的端值之一。他并不是一位一位的建立结果的。相比总是返回T或者nil的anyoddp，他从不增强他的结果。
8.12 基本模板中的变量
到现在为止我们学习的模板是有很多用处的，使用它们的具体方式在lisp编程中特别的普遍或者贴别值得注意。在本节中我们会讲解基本模板中的变量。
8.12.1 列表组合递归
在lisp中使用最频繁的就是列表组合递归。增强递归的特殊情况就在增强函数是cons。我们创造一个新的内存单元，作为每一个递归调用的返回。因此，递归的深度就等于结果中内存单元链条的长度，在加上1.（因为最后一个调用返回nil，而不是一个内存单元）。
8.12.2 多个变量的同时递归
多个变量的同时递归是一个任何递归模板的直接扩展。不是只有一个输入，函数有多个，一个或多个输入会被递归调用。例如，假设我们想要写一个nth函数的递归版本，叫做mynth，。回顾一下 ,(NTH 0 x)就是(FIRST x)，这告诉我们哪一个端测试会被使用。随着每一个递归调用，我们接受列表x的后续rest一步步进行处理。结果函数显示了单测试尾递归是在两个变量的同时递归。这个模板在图8-5中有显示。下面是追踪两个变量同时被处理的过程。
8.12.3 条件增强型
在一些列表处理问题中，我们想要跳过某些特定元素，只是用其中一部分来计算结果。这就是条件增强型。例如，在extract-symbols中，只有那么是字符的元素才会被包含在结果中。
在extract-symbols的函数体中，包括了两个递归调用。一个调用时嵌套在一个增强表达式中的，这样是讲一个新的元素组合进现有的结果中。另一个调用是非增强的，结果只是简单返回了。在后续的追踪输出中你会注意到有些时候两个相继的调用时饭回一个值，这是因为每一对调用都选择了那个非增强的语句，当增强语句被选择，结果页不在相同。
8.12.4 多递归
如果一个函数在每一个调用中制造了超过一个递归调用的话，函数就是多递归的。（不要和多个同时递归混淆了，之前的只是将多个变量进行同时处理，并不在每一个调用中使用多个递归。）斐波那契函数是一个景点的多递归例子，fib（n）调用自身两次，依次是fib（n-1），另一次是fib（n-2）。两次调用的结果使用+来结合。
将多递归的过程具象化的一个好方法就是看追踪输出的嵌套调用的形状。我们来定义，终极调用的意思就是不再往更深的地方递归了，在先前所有的函数中，连续调用严格来说是一个个嵌套在里面的，内部的最终调用也是一个终极调用。然后，从内到外的直接返回值。但是由于多递归函数FIB的使用，每一个调用都会产生两个新的调用，这两个是内嵌在现有的调用中的，但是他们不能互相嵌套。并不是一步步出现在上层调用中，多递归函数因此有很多终极调用。在接下来的追踪输出中，有三个终极调用，两个非终极调用。
8.13 树和car/cdr递归
有时候我们想要来处理一个嵌套列表中的所有元素，而不仅仅是顶层元素。如果列表时不规则形状的，比如(((GOLDILOCKS . AND)) (THE . 3) BEARS)，这样可能会更加困难了。当我们来写自己的函数，我们不知道输入会有多长或者嵌套会有多复杂
解决这个问题的技巧并不是去考虑这个函数的输入是不规则的嵌套列表，而是考虑一颗二进制树的结构（请见下面的插图）二进制数是很规则的，每一个节点不是元字符就是两个分支的组合，car和cdr。因此我们的函数所做的就是处理元字符，递归调用自身来处理每一个节点的car和cdr。这个技术叫做car/cdr递归；这是多递归的特殊情况。
举个例子，假设我们想要一个函数find-number来搜索一个树，并返回出现的第一个数字，没有的话就返回nil。然后我们应该使用numberp和atom作为我们的终端测试，还有or来做组合器。请注意or是一个条件，只要有一个or语句被求值为true，or就会停止然后返回那个值。因此我们不是一定要搜索整个树；函数有可能停止递归，只要第一个非nil的值出现。
除了树搜索，另一个car/cdr递归的广泛使用的地方时通过使用cons构造器来建造树。例如，有一个函数接受树作为输入然后返回一个新的树，结果中所有的非nil元字符都被替换成字符Q。
8.14 使用辅助函数
对于一些问题来说，构造解决方案是一个递归函数加上一个辅助函数式很有用的。递归函数做大部分工作。副主函数是你从顶层的调用之一。他提供的是一些在递归开始或者结束后的特殊服务。例如，加入我们想要写一个函数count-up来数数，从1到n。
这个问题比count-down要难一些，因为内部的递归次奥用必须是输入到达5的时候结束递归（而不是0）。一般来说，最简单的方法就是去支持递归函数的原始值所以他能决定什么时候停止。我们必须支持一个附加的参数。那就是一个计数器，来告诉我们函数的递归由多深了。副主函数的工作就是提供计数器的原始值。
8.15 艺术和文学中的递归
递归不止在计算机编程中出现，也会在文学故事和画作中有出现。经典的一千零一夜故事中就包括故事中的故事中的故事,他给出了一种递归的趣味性。在视觉上的相似表达出现在苏斯鄙视的注明画作《戴高帽的猫》里。猫的帽子里是另一只戴着帽子的猫，就如此递归。
一些最有想象力的递归展现和自我引用的表达是荷兰艺术家M.C.Escher的版画《画手》。
小结
递归是一个非常强大的控制结构，也是计算机科学中最重要的概念。如果一个函数会调用自身，那么他就被成为是递归的。为了写一个递归函数，我们必须解决龙提出的三个规则引出的问题。
- 知道什么时候停止
- 决定如何进行下一步
- 将整个过程拆分成为更小的过程加上简单步骤
我们在本章学习了很多递归模板，递归模板触及的是常规递归问题的本质。他们会在函数定义的时候被使用，或者在分析现有函数的时候被使用。下面是现在为止学到的递归模板：
- 双测试尾递归Double-test tail recursion.
- 单测试尾递归Single-test tail recursion.
- 单测试增强型Single-test augmenting recursion.
- 列表组合型List-consing recursion.
- 多变量的同时递归Simultaneous recursion on several variables.
- 条件增强型Conditional augmentation.
- 多递归调用Multiple recursive calls.
- cad/cdr递归CAR/CDR recursion.
Lisp Toolkit: The Debugger
所有的Lisp初学者都会学习一个debugger命令，因为只要输入错误了，就会进入debugger，就不得不使用命令出来！lisp实现在debugger方面本质上差别很大，所以从错误中返回也没有一个统一的标准。一些人肯呢过已经尝试输入q或者quit或者：a来尝试abort。其他人可能使用ctrl-c或者ctrl-g组合键。在任何情况下，你都可以退出来，但是为什么不对呆一会儿呢？
debugger并不是真的吧你程序里的bug给移除了。他所做的是让你在错误发生的时候检查计算过程的状态。这也使得它成为一个学习递归的好工具。我们可以使用break函数来进入debugger，所处的是计算过程的一个断点。break的参数是一个消息，被字符串引用，当进入debugger的时候就会打印出来，下面是一个fact的修改后版本来显示break的使用。
现在我们就在debugger中了，“Debug>”就是提示符。（你的debugger也许是用不同的提示符）。我们能做的其中一件事情就是展现控制栈的回溯，会展现所有的现在栈中的递归调用。如果你对“控制栈”和“栈帧”等术语不熟悉的话，只要在debugger中慢慢摸索就可以渐渐掌握诀窍了。（控制栈是lisp追踪嵌套函数调用的方式，一个栈帧就是描述其中一个函数调用的入口），在我们的debugger中，展现回溯的命令就是bk。
bk命令的变量允许不同种类的控制栈信息展现。在我的debugger中，bkfv就会给出一个函数名字和本地变量的表示。
在debugger内部的时候，我们可以看到变量的值，并且可以使用任意的lisp表达式来使用它们。
当我们进入debugger，我们正在栈的顶层。我们可以使用命令进入栈内，往上或者往下移动。如果我们向下移动，我们会看到其他叫做n的本地变量。
最后，我们使用debugger来从任何栈中的调用返回。这导致的计算会好像函数正常返回了一样。
当我们从当前栈帧返回10的时候，计算过程假定在那个点，产生的值是5×4×3×10 = 600
你的debugger也许和我的看上去并不是完全相同，也许提供某些不一样的功能，但是检查控制栈这个基本思想在所有lisp中是一样的。你可以看看你的lisp用户手册来看看自己的实现支持那些命令。键入help或者：h或者？来看看你的debugger有那些命令。
第八章进阶话题
8.16 尾递归的优点
请记住尾递归函数在递归调用之后是没有任何动作的，递归函数返回什么，他就返回什么。anyoddp就是一个为递归函数，但是count-slices就不是。如果我们追踪count-slices来看，我们会看到每一个调用都会产生一个不同的返回值（由于增强的原因）。在一个尾递归函数中，所有的调用在终极调用中都是返回同一个值。
一般来说，只要可能的话，写递归函数最好就是用尾递归，因为lisp系统可以比普通递归函数更有效率地执行尾递归函数。他们用一个跳转来代替递归调用。很多lisp编译器都是自动优化的，一些解释器也是。
创造一个普通函数的尾递归版本最普遍的做法就是引入一个附加变量来积累增强的值。例如，下面一个例子：
在追踪TR-COUNT-SLICES的时候，你会注意到n的值是随着每一个调用而增长的。终极调用计算出返回值，4；这个值会不加更改的传回去。
另一个增强型如何被消除的方法就是引入一个附加变量，这个例子就是reverse函数。为了反转一个长度为n的列表，我们可以递归反转列表的剩余部分，然后确定第一个元素。
但是这个定义并不是尾递归，在递归调用返回后，结果被append增强，reverse的双输入，尾递归定义，就是使用一个附加的变量来建立结果。
并不是所有的函数都有尾递归版本，任何多递归函数，比如fib，就不能够简单转换为尾递归，在第一个递归结束后，还有代码等着去执行。
8.17 写一个新的函数式操作
我们可以使用funcall来调用一个用户支持的函数。这允许我们去写一个我们自己的函数式操作。例如，下面的mapcar的简单版本就只是支持简单列表。
我们的所提供的函数my-mapcar必须是一个单输入函数，多少输入都会被funcall调用。
8.18 特殊函数labels
到现在为止我们已经写过像独立的defun这样的辅助函数。这有点单薄了，既然辅助函数是定义在顶层，那么就又能被其他函数误调用。第二，更加严重的问题是辅助函数使用defunct定义的，导致他看不到任何主函数的本地变量。这些问题都将被label解决。
特殊函数labels允许我们在主函数内部定义一个本地函数，就像乐天能让我们建立本地变量一样。这两个语法格式是相似的。
这个函数体可以调用任何本地变量。本地函数可以互相调用，也可以指向上层的变量。
In the following example, notice that COUNT-UP-RECURSIVELY
references N, the input to COUNT-UP
请注意，接下来的例子count-up-recursively指向n，count-up的输入。
使用labels的一个缺点就是在大部分的lisp实现当中，在内部定义的一个labels表达式是不能被追踪的函数。但是你仍然可以使用step来步进追踪手动求值，如果需要的话。
8.19 递归数据结构
本章被用来讲解用递归定义函数，数据结构也有递归定义。考虑下接下来的s表达式定义（字符表达式）：
S表达式这个属于是被用在自身定义的内部。这个就是递归数据结构，S表达式就是一个应用十分广泛的递归数据结构实例，在计算机科学的所有领域都有十分重要的应用，叫做树。还有另一个树的例子，这一次表现是数学表达式。
树底部的节点叫做终极节点，因为他们没有任何分支子节点。剩下的节点被叫做非终极节点，一棵树可以被递归定义：
树很自然的由列表来表现。列表（（3 + 5）-（8 + 6））对应的树，我们来看看另一个数学表达式：
这个树表述的事实是这样，一个非终极节点的分支需要有同样的长度。表达式((2 + 2) - (3 *(4 * (12 / 6))))的列表表示我们可以递归定义如下：
