-
棧溢出
鎖定
- 中文名
- 棧溢出
- 屬 性
- 緩衝區溢出的一種
棧溢出定義
棧溢出就是緩衝區溢出的一種。 由於緩衝區溢出而使得有用的存儲單元被改寫,往往會引發不可預料的後果。程序在運行過程中，為了臨時存取數據的需要，一般都要分配一些內存空間，通常稱這些空間為緩衝區。如果向緩衝區中寫入超過其本身長度的數據，以致於緩衝區無法容納，就會造成緩衝區以外的存儲單元被改寫，這種現象就稱為緩衝區溢出。緩衝區長度一般與用户自己定義的緩衝變量的類型有關。
棧溢出就是緩衝區溢出的一種。
在pascal語言中，棧溢出的錯誤代碼為202號錯誤。
在Python中，函數調用是通過棧（stack）這種數據結構實現的，每當進入一個函數調用，棧就會加一層棧幀，每當函數返回，棧就會減一層棧幀。由於棧的大小不是無限的，所以，遞歸調用的次數過多，會導致棧溢出。
例子如下：
def fact(n):
if n==1:
return 1
return n * fact(n - 1)
>>> fact(1000)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 4, in fact
...
File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded in comparison
棧溢出解決方法
解決遞歸調用棧溢出的方法是通過尾遞歸優化，事實上尾遞歸和循環的效果是一樣的，所以，把循環看成是一種特殊的尾遞歸函數也是可以的。
如上棧溢出例子，由於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在函數調用前就會被計算，不影響函數調用。尾遞歸調用時，如果做了優化，棧不會增長，因此，無論多少次調用也不會導致棧溢出。
