執行棧

執行棧是計算機科學中存儲有關正在運行的子程式的訊息的棧。有時稱控制棧（control stack）、運行時棧（run-time stack）和調用棧，但棧中不一定僅存儲子程式訊息。幾乎所有電腦程式都依賴於執行棧，然而高級語言一般將調用棧的細節隱藏至後台。

基本介紹

• 中文名：執行棧
• 外文名：execution stack
• 學科：計算機
• 定義：存儲有關運行的子程式的訊息的棧
• 有關術語：棧
• 領域：計算機系統

簡介

執行棧是計算機科學中存儲有關正在運行的子程式的訊息的棧。經常被用於存放子程式的返回地址。在調用任何子程式時，主程式都必須暫存子程式運行完畢後應該返回到的地址。因此，如果被調用的子程式還要調用其他的子程式，其自身的返回地址就必須存入執行棧，在其自身運行完畢後再行取回。在遞歸程式中，每一層次遞歸都必須在執行棧上增加一條地址，因此如果程式出現無限遞歸（或僅僅是過多的遞歸層次），執行棧就會產生棧溢出。

棧

棧(stack)是限定僅在表尾進行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義，稱為棧頂(top)，相應地，表頭端稱為棧底(bottom)。

棧也可以是指計算機記憶體中由程式指定的一個後進先出(LIFO)存儲區或CPU內部的一個LIFO暫存器組。前者稱軟棧，後者稱硬棧。軟棧的一端是固定的，另一端是浮動的，浮動的一端稱為棧頂。所有信息的存入和取出都只能在棧頂進行，而且是在堆疊指示字暫存器的配合下，按LIFO原則工作的。硬棧棧頂一端是固定的，壓入的數據項占據棧頂，棧中原有的數據項都依次向棧底方向移動；彈出數據時，最後進棧的數據項先被彈出，下面各級數據項依次向棧頂方向移動。軟棧和硬棧功能均相同，主要作為LIFO緩衝存儲器，用於中斷處理、子程式嵌套及暫存數據。在程式中斷時，堆疊(自動)保存程式計數器、狀態暫存器及工作暫存器的內容，並在中斷結束後把這些現場內容恢復到相應的暫存器中。

功能

執行棧的主要功能是存放返回地址。除此之外，調用棧還用於存放：

本地變數：子程式的變數可以存入調用棧，這樣可以達到不同子程式間變數分離開的作用。

參數傳遞：如果暫存器不足以容納子程式的參數，可以在調用棧上存入參數。

環境傳遞：有些語言（如Pascal與Ada）支持“多層子程式”，即子程式中可以利用主程式的本地變數。這些變數可以通過調用棧傳入子程式。

在較底層語言（如彙編語言與C語言中），程控訊息與數據可能一同被存入調用棧中，因此造成安全隱患，可能允許惡意程式通過棧緩衝區溢出(stack buffer overflow)來獲取程式的控制權。

堆疊溢出

堆疊溢出（英語：stack overflow）在計算機科學中是指使用過多的記憶體時導致調用堆疊產生的溢出[1]。堆疊溢出的產生是由於過多的函式調用，導致調用堆疊無法容納這些調用的返回地址，一般在遞歸中產生。堆疊溢出很可能由無限遞歸（Infinite recursion）產生，但也可能僅僅是過多的堆疊層級。

堆疊溢出在核心設計中尤其危險，因此很多入門核心設計教程建議用戶不要嘗試使用遞歸程式；而是基於安全和性能考量，改用循環處理問題。

遞歸

概述

是計算機問題求解的一種算法.是一種處理過程，這種過程的某一步要用到它自身的上一步(或上幾步)的結果。一個直接或間接地調用自己的過程稱為遞歸過程.在本過程中出現調用本過程自身的過程稱為直接遞歸過程；若過程P包含著對另一過程Q的引用，而Q又直接或間接地引用P，則稱P為間接遞歸過程。一個使用函式自身給出定義的函式稱為遞歸函式。在數學定義和計算機算法中，遞歸技術是一種特別有力的工具。遞歸函式或遞歸過程的套用往往使函式的定義和算法的描述比使用非遞歸方法更簡明。

遞歸過程

在程式設計中，使一個過程本身用 作一個子過程，這一做法往往是很方便的。如果過程這樣做，就稱為遞歸的。在處置符號表達式中，遞歸 過程尤為自然，因為這樣的程式結構與數據結構相匹配。至於程式設計語言，遞歸過程是十分自然的；在語言的定義中要求一個專門的語句來禁止它們。 但是，它們的實現就要求編譯一個特種的目標代碼， 象Fortran這樣的早期程式設計語言中是不容許的。 問題在於：程式中的變數與機器中的存儲單元相對應，當程式被它本身調用時，它將使用這些相同的存儲單元，改寫它們原先的內容。所以，遞歸程式使用 一個稱為棧的數據結構，用來把必須保存的暫存器內容存儲起來。這一存儲可在進入子例程之前由調用程式來完成，或者可在使用這些暫存器之前由子例程來完成，後者較常用。

在暫存器已保存在棧上之後，進入棧的索引增大到存儲的暫存器數，因而棧上其後的保存將使用新的寄器。當存在子例程時，保存的暫存器的內容從棧恢復到它們原先的值，棧指針按其原先增加的量減少。這項工作是根據如何存入的而通過相應的 調用程式或子例程來完成的。另一種方法是使用棧作所有的暫時暫存器。在這種情況下，無需把數據傳來傳去，只需在子例程進入與離開時改變棧指針。但是，這種方法對某些機器可能會用盡它的索引能力， 而這能力也是其他用途所需要的。遞歸程式可用任 何程式設計語言通過顯式地把保存和恢復進行程式 設計的方法來編寫。在常規基礎上使用遞歸子例程的第一個語言是 Newell、Shaw和Simon的IPL語言。用表當作棧使 用，保存與恢復顯然由程式設計師完成。第一個提供用於 遞歸的自動機構是Lisp。Algol和其後繼者Pascal和 Ada也容許遞歸，APL、PL/I、C和Snobol等其他語 言也一樣。許多計算機有處置棧的專用指令(例如，Digital Equipment DEC-10的PUSH和POP指令)。其他機器，例如Burroughs B5000和其後繼者，具有直接使用硬體棧的指令。這些專用的設施對於遞歸程式設計的效率有適度的增加。