栈溢出，计算机术语之一

定义

栈溢出就是缓冲区溢出的一种。由于缓冲区溢出而使得有用的存储单元被改写，往往会引发不可预料的后果。程序在运行过程中，为了临时存取数据的需要，一般都要分配一些内存空间，通常称这些空间为缓冲区。如果向缓冲区中写入超过其本身长度的数据，以致于缓冲区无法容纳，就会造成缓冲区以外的存储单元被改写，这种现象就称为缓冲区溢出。缓冲区长度一般与用户自己定义的缓冲变量的类型有关。

栈溢出就是缓冲区溢出的一种。

在pascal语言中，栈溢出的错误代码为202号错误。

在Python中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

例子如下：

def fact(n):

if n==1:

return 1

return n * fact(n - 1)

u003eu003eu003e fact(1000)

Traceback (most recent call last):

File u003cstdinu003e, line 1, in u003cmoduleu003e

File u003cstdinu003e, line 4, in fact

...

File u003cstdinu003e, line 4, in fact

RuntimeError: maximum recursion depth exceeded in comparison

解决方法

解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。

尾递归是指，在函数返回的时候，调用自身本身，并且， return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

如上栈溢出例子，由于fact(n)函数return n * fact(n - 1)引入了乘法表达式，所以就不是尾递归了。要改成尾递归方式，需要多一点代码，主要是要把每一步的乘积传入到递归函数中：

def fact(n):

return fact_iter(n, 1)

def fact_iter(num, product):

if num == 1:

return product

return fact_iter(num - 1, num * product)

可以看到，return fact_iter(num - 1, num * product)仅返回递归函数本身，num - 1和num * product在函数调用前就会被计算，不影响函数调用。尾递归调用时，如果做了优化，栈不会增长，因此，无论多少次调用也不会导致栈溢出。

性质

由于缓冲区溢出而使得有用的存储单元被改写，往往会引发不可预料的后果。向这些单元写入任意的数据，一般只会导致程序崩溃之类的事故，对这种情况我们也至多说这个程序有bug。但如果向这些单元写入的是精心准备好的数据，就可能使得程序流程被劫持，致使不希望的代码被执行，落入攻击者的掌控之中，这就不仅仅是bug，而是漏洞(exploit)了。