深入理解递归算法，被误解的递归 _递归算法

递归是一个神奇的算法，它是编程书籍中讲解的最尴尬部分。这些书籍通常会展示一个递归的阶乘实现，然后警告你，虽然它能运行但是它非常的慢并且可能会堆栈溢出而崩溃。虽然大家对它持怀疑态度，但是这不影响递归是算法中最强大的想法。
让我们来看看经典的递归阶乘：
factorial.c

#include <stdio.h>int factorial(int n){ int previous = 0xdeadbeef; if (n == 0 || n == 1) { return 1; } previous = factorial(n-1); return n * previous;}int main(int argc){ int answer = factorial(5); printf("%dn", answer);} 一个函数调用自身的想法起初非常神秘。为了解释整个过程，下图展示了factorial(5)被调用到n == 1 栈上结构。

文章插图

每次调用factorial都会生成一个新的栈帧。这些栈帧的创建和销毁使得递归因子比其迭代部分慢。在调用开始和返回之前的这些栈帧累积是可能耗尽栈空间并使程序崩溃。
但是这些担忧通常是理论上的。例如，栈帧 factorial每个占用16个字节（这可以根据栈对齐和其他因素而变化）。如果您在计算机上运行现代x86 linux内核，通常默认有8兆字节的堆栈空间，因此factorial n最多可以处理512,000 。这是一个巨大数，需要8,971,833位来表示这个数，所以栈空间是我们问题中最少的：一个微弱的整数 - 甚至是64位 - 在我们用完栈空间之前会溢出数万次。
我们稍后会看一下CPU的使用情况，但是现在让我们从位和字节中退一步，看看递归作为一种通用技术。我们的阶乘算法归结为将整数N，N-1，... 1推入堆栈，然后以相反的顺序将它们相乘。我们使用程序的调用堆栈执行此操作的前提是：我们可以在堆上分配堆栈并使用它。虽然调用堆栈确实具有特殊属性，但它只是您可以使用的另一种数据结构。
一旦你看到调用堆栈作为一个数据结构，其他东西就变得豁然开朗了：将本身之前所有这些整数累加起来