递归函数的致命缺陷：巨大的时间开销和内存开销(附带优化方案)

递归函数是一种强有力的技巧?用来解决某些问题很顺手?比如前面提到的求阶乘、求菲波那契数?但是和其他技巧一样?递归函数也是有缺陷的?而且这种缺陷是致命性的。

递归函数的空间开销

在程序占用的整个内存中?有一块内存区域叫做栈?Stack??它是专门用来给函数分配内存的?每次调用函数?都会将相关数据压入栈中?包括局部变量、局部数组、形参、寄存器、冗余数据等。

栈是针对线程来说的?每个线程都拥有一个栈?如果一个程序包含了多个线程?那么它就拥有多个栈。目前我们编写的程序都是单线程的?所以不必考虑多线程的情况。

对每个线程来说?栈能使用的内存是有限的?一般是 1M~8M?这在编译时就已经决定了?程序运行期间不能再改变。如果程序使用的栈内存超出较大值?就会发生栈溢出?Stack Overflow?错误。

栈内存的大小和编译器有关?编译器会为栈内存指定一个较大值?在 VC/VS 下?默认是 1M?在 C-Free 下?默认是 2M?在 Linux GCC 下?默认是 8M。当然?我们也可以通过参数来修改栈内存的大小。

发生函数调用时会将相关数据压入栈中?函数调用结束会释放这一部分内存?对于一般的函数来说?这不会有任何问题?但是对于递归函数?这会导致严重的问题?

递归函数内部嵌套了对自身的调用?除非等到最内层的函数调用结束?否则外层的所有函数都不会调用结束。通俗地讲?外层函数被卡主了?它要等待所有的内层函数调用完成后?它自己才能调用完成。

每一层的递归调用都会在栈上分配一块内存?有多少层递归调用就分配多少块相似的内存?所有内存加起来的总和是相当恐怖的?很容易超过栈内存的大小限制?这个时候就会导致程序崩溃。

例如?一个递归函数需要递归 10000 次?每次需要 1KB 的内存?那么最终就需要 10MB 的内存。

为了演示由于栈溢出而导致程序崩溃的情形?下面我们用递归的方式来求 1+2+3+ ...... + (n-1) + n 的值+

在 Visul Studio 下运行该程序=稍等片刻后就看到程序崩溃了=如下图所示=

这是因为=每次递归调用都需要超过 1KB 的内存=仅仅数组就占用了 1KB 内存==而要得到最终的结果需要 1000 次递归调用=这样一来=所有内存的总和就超过了 1MB。

上面我们说过=Visual Studio 默认的栈内存只有 1MB=超过这个界限程序就无法运行了=只能让它崩溃。使用其它的编译器也许程序不会崩溃=读者可以亲自尝试。

递归函数的时间开销

每次调用函数都会在栈上分配内存=函数调用结束后再释放这一部分内存=内存的分配和释放都是需要时间的。

每次调用函数还会多次修改寄存器的值=函数调用结束后还需要找到上层函数的位置再继续执行=这也是需要时间的。

所有的这些时间加在一起是非常恐怖的。

下面我们以「求斐波那契数」为例来演示双层递归的时间开销。

运行结果=

Input a number: 42↙

Fib(42) = 267914296

run time: 13.137000s

可以看到=为了求 42 的斐波那契数程序竟然运行了 13 秒=简直让人发指。

使用迭代来替换递归函数

既然递归函数的解决方案存在巨大的内存开销和时间开销=那么我们如何进行优化呢=

其实=大部分能用递归解决的问题也能用迭代来解决。所谓迭代=就是循环。

许多问题是以递归的形式进行解释的=这只是因为它比非递归形式更为清晰。但是=这些问题的迭代实现往往比递归实现效率更高=虽然代码的可读性可能稍差一些。

与递归函数相比=迭代不但没有额外的内存开销=也没有额外的时间开销。

下面我们分别用递归和迭代的方案来求斐波那契数=看看它们究竟孰快孰慢。

运行结果=

Input a number: 42↙

Fib_recursion(42) = 267914296

run time with recursion: 13.173000s

Fib_iteration(42) = 267914296

run time with iteration: 0.000000s

你看=递归用了 13 秒=迭代几乎瞬间完成=接近0秒==迭代比递归快成千上万倍=这个差异是巨大的。

总结

函数调用本来就存在内存开销和时间开销=递归一次这种开销就增加一倍=如果有成千上万次的递归=那么所有开销的总和就是巨大的。这是递归的致命缺陷=无法优化。所以建议大家尽量少用递归=能用迭代就用迭代吧。