递归是一个神奇的算法，也是编程书籍讲解的最囧的部分。这些书通常会展示阶乘的递归实现，并警告您虽然它运行起来非常慢，并且可能会因堆栈溢出而崩溃。虽然大家对此持怀疑态度，但这并不影响递归是算法中最强大的思想。我们来看看经典的递归阶乘：factorial.c#includeintfactorial(intn){intprevious=0xdeadbeef;if(n==0||n==1){return1;}previous=factorial(n-1);returnn*previous;}intmain(intargc){inanswer=factorial(5);printf("%d\n",answer);}函数调用自身的想法一开始很玄乎。为了解释整个过程，下图显示了在n==1堆栈结构上调用factorial(5)。每次调用factorial都会生成一个新的堆栈框架。这些堆栈帧的创建和销毁使得递归因子比它的迭代部分慢。在调用开始和返回之间累积这些堆栈帧很可能会耗尽堆栈空间并使程序崩溃。但这些担忧通常是理论上的。例如，堆栈帧阶乘每个占用16个字节（这可能因堆栈对齐和其他因素而异）。如果您在计算机上运行现代x86Linux内核，默认情况下通常有8兆字节的堆栈空间，因此阶乘n最多可以处理512,000。这是一个巨大的数字，需要8,971,833位来表示该数字，因此堆栈空间是我们问题中最少的：一个微不足道的整数-即使是64位-在我们用完堆栈空间之前也会溢出数万次。稍后我们将查看CPU使用情况，但现在让我们从位和字节退后一步，将递归视为一种通用技术。我们的阶乘算法归结为将整数N,N-1,...1压入堆栈，然后以相反的顺序将它们相乘。我们对程序的调用栈这样做的前提是我们可以在堆上分配栈并使用它。虽然调用堆栈确实具有特殊属性，但它只是您可以使用的另一种数据结构。一旦您将调用堆栈视为一种数据结构，其他事情就会变得清晰：将所有这些整数在其自身之前相加并与自身相乘显然不是一个明智的选择。使用迭代过程来计算阶乘更为明智。有一个传统的面试题，你把一只老鼠放在迷宫里，你帮助老鼠找到奶酪，假设老鼠可以在迷宫中向左或向右转。你将如何建模和解决这个问题？像生活中的大多数问题一样，您可以将这只啮齿动物的任务抽象成一个图，具体来说是一个二叉树，其中的节点代表迷宫中的位置。然后你可以让鼠标左转到尽头，走到死胡同时原路返回，再右转。下图是鼠标的路径：每条边（线）可以左转或右转，鼠标可以选择。如果任何转弯被阻挡，则相应的边缘不存在。无论您使用调用堆栈还是其他数据结构，这个过程本质上都是递归的。但是使用调用栈非常简单：Maze.c#include#include"maze.h"intexplore(maze_t*node){intfound=0;if(node==NULL){return0;}if(node->hasCheese){return1;//foundcheese}found=explore(node->left)||explore(node->right);returnfound;}intmain(intargc){intfound=explore(&maze);}在迷宫中。c：找到13中的奶酪，下图就是一叠。虽然这里很难摆脱递归，但这并不意味着它必须通过调用堆栈来完成。例如，您可以使用字符串RRLL来跟踪转弯，并依靠该字符串来确定鼠标的下一步行动。或者您可以分配其他变量来记录奶酪狩猎的状态。您仍然在实施递归过程，但使用您自己的数据结构。这可能会更复杂，因为调用堆栈就像手套一样。每个堆栈帧不仅记录了当前节点，还记录了该节点中的计算状态（在这种情况下，我们是只取了左边还是尝试了右边）。然而，我们有时会因为害怕溢出而放弃好东西。在我看来非常愚蠢。我们可以看到，栈很大，栈空间之前往往还有其他的约束。还要检查问题的大小并确保可以安全地处理它。CPU的担忧主要是由两个广泛的病态示例引起的：愚蠢的因素和可靠的O(2n)递归Fibonacci没有内存。这些并不代表一个健全的堆栈递归算法。实际情况是堆栈操作很快。数据偏移是准确的，堆栈在缓存中，不需要冷启动，并且有专门的指令来完成这项工作。同时，使用您自己的堆分配数据结构会产生大量开销。会看到其他人写的东西比调用堆栈递归更复杂，性能更差。现代CPU非常好，它们通常不是瓶颈。简单性通常等同于性能。
