递归和尾递归

在听老师讲课的时候，老师提到了尾递归这一概念，脑海里隐约有些印象，仿佛在哪本数据结构算法中见过这一概念，但是又没有认真理解到尾递归和普通递归的区别在哪儿。在听完老师的讲解，还有和小伙伴们的讨论以后，决定写下一篇笔记，记录一下自己的理解。

下面来看两个简单的小故事：

故事一：翠花想知道男神Jack的出生年月是什么。因此跑去问Jack的同事二狗子，二狗子说：“我知道他的1998出生，剩下的你要问铁柱了”；接着翠花找到了铁柱，铁柱说：“Jack好像是6月份出生的，具体是哪天我就不知道了，不过你可以问问狗剩儿”。说罢就朝着屋子里面吼了两句“狗剩儿！狗剩儿！Jack的生日是哪天？”，狗剩从屋子里跑了出来，“啥？Jack？Jack谁啊，我怎么知道他生日”狗剩儿有些懵逼，铁柱一巴掌呼狗剩儿脑袋上“就是大毛，你四不四傻”，狗剩摸着脑袋小声的咕噜到“他不是叫Tony嘛”，铁柱似乎有些不耐烦了“你咋这墨迹呢，麻溜的，几号？！”，畏惧着铁柱的淫威，狗剩儿留下了屈辱的泪水“24号”，这时，远处传来了一阵阵呼喊声“Tommy，Tommy，Tommy~~狗剩儿，你大爷的，赶紧给老子过来，有人要理发”。不管狗剩如何，铁柱知到了Jack是24号生日，结合自己知道的6月份，告诉了二狗子，二狗子知道Jack6月24号生日，结合自己知道的1998年，告诉了翠花Jack生日是1998年6月24日。

嘿嘿，小小地调侃一下那些把我头发剪得乱七八糟的理发师们，一个故事看不出什么区别，我们来看看第二个。

故事二：翠花想知道男神Jack的出生年月是什么。因此跑去问Jack的同事二狗子，二狗子说：“我就知道他是1998年出生的，我帮你问问铁柱”，接着二狗子找到了铁柱“Jack是1998年出生的，你知道几月几号不？知道告诉翠花”，铁柱说：“Jack是1998年出生的啊，我还不知道呢，我只知道他是6月份出生的，我帮你问问狗剩”，接着铁柱找到了狗剩儿“Jack是1998年6月份出生的，你知道具体哪天不？知道告诉翠花”，狗剩儿说：“原来Jack是1998年6月份出生的啊，我还不知道，我就知道他是24号”，接着狗剩把这个消息告诉了翠花。

大家也看出来了，这两个故事讲的是同一件事，但是确实用的两种不同的方法，翠花相当于一个程序，她需要执行一个函数，也就是“知道男神生日”这个函数。二狗子，铁柱，狗剩分别代表参数不同的同一种函数，即“知道男神生日”

第一个故事就相当于普通递归，首先执行二狗子的函数，二狗子知道生日的一部分+铁柱的函数，然后剩下的执行铁柱的函数，铁柱知道一部分+狗剩的函数，然后执行狗剩儿的函数，狗剩儿将执行结果返回给铁柱，，铁柱将狗剩返回的结果结合自己知道的一部分，返回给二狗子，二狗子结合自己知道的一部分，将结果返回给了翠花。

第二个故事就相当于尾递归，首先执行二狗子的函数，然后二狗子将自己知道的一部分传给铁柱，铁柱将二狗子传来的参数结合自己知道的，传给了狗剩儿，狗剩将铁柱传过来的信息结合自己知道的，得到最后的结果，男神的生日，最后将结果返回给了翠花。

从计算机执行过程上来看，普通递归有一个特别大的弊端，他需要记录每次递归调用的结果，这种记录，即入栈当前函数帧。直到执行到函数的出口，再一次一次出栈，将所有结果连接起来，返回给程序。如果如同故事一样只有三层，普通递归和尾递归区别不大，但是如果需要记录的结果太多，比如计算十亿的阶乘，他就需要入栈近十亿次，栈就会过大，就会造成“栈溢出”，消耗了太多的资源。

尾递归就解决了这种问题，他不需要记录每次的递归调用，因为他把当前执行结果作为参数，传进了下一次递归调用，在函数帧入栈时，因为前一次结果已经传入了当前次，前一次函数帧已经没有用处，当前次函数帧可以覆盖掉前一次函数帧，最后结果直接返回最新一次函数帧中的结果。