遞歸過程
出自 MBA智库百科(https://wiki.mbalib.com/)
目錄 |
遞歸過程指棧的另一個重要應用是在程式設計語言中實現遞歸過程。一個直接調用自己或通過一系列的過程語句間接地調用自己的過程，稱做遞歸過程。遞歸是程式設計中一個強有力的工具。
一個直接調用自己或通過一系列的過程調用語句間接調用自己的過程，稱作遞歸過程。
當一個過程的運行期間調用另一個過程時，在執行被調用過程之前，系統需先完成如下三件事：
1、將所有的實在參數，返回地址等信息傳遞給被調用的過程保存。
2、為被調用過程的局部變數分配存儲空間。
3、將控制轉移到被調用入口。
從被調過程返回調用過程
1、保存被調用過程的計算結果。
2、釋放被調用過程的數據區。
3、依照被調過程保存的返回地址將控制轉移到調用過程。
服從後調用先返回的原則。
基本原理是重覆的把原問題轉換為相似的新問題，直到把問題解決為止。
關鍵點：
1、用較簡單的問題來表示較複雜的問題。
2、不能產生自己調用自己的無窮序列。即必須要有一個是遞歸出去的出口。。
遞歸的調用時通過棧來實現的。
“遞歸”過程是指調用自身的過程。通常，這不是編寫VisualBasic代碼的最有效方法。
其一，有很多數學函數是遞歸定義的，如大家熟悉的階乘函數Fact（n）=1若n=1Fact（n）=n·Fact（n-1）若n>12階Fibonacci數列Fib（n）=0若n=0Fib（n）=1若n=1Fib（n）=Fib（n-1）+Fib（n-2）其它情形和ackerman函數Ack（m，n）=n+1m=0Ack（m，n）=Ack（m-1，1）n=0Ack（m，n）=Ack（m-1，Ack（m,n-1））其它情形等；
其二，有的數據結構，如二叉樹，廣義表等，由於結構本身固有的遞歸特性，則它們的操作可遞歸地描述；
其三，還有一類問題，雖則問題本身沒有明顯的遞歸結構，用遞歸求解比迭代求解更簡單，如八皇後問題，Hanio塔問題等。
限制條件。您在設計一個遞歸過程時，必須至少測試一個可以終止此遞歸的條件，並且還必須對在合理的遞歸調用次數內未滿足此類條件的情況進行處理。如果沒有一個在正常情況下可以滿足的條件，則過程將陷入執行無限迴圈的高度危險之中。
記憶體使用。應用程式的局部變數所使用的空間有限。過程在每次調用它自身時，都會占用更多的記憶體空間以保存其局部變數的附加副本。如果這個進程無限持續下去，最終會導致StackOverflowException錯誤。
效率。幾乎在任何情況下都可以用迴圈替代遞歸。迴圈不會產生傳遞變數、初始化附加存儲空間和返回值所需的開銷，因此使用迴圈相對於使用遞歸調用可以大幅提高性能。
相互遞歸。如果兩個過程相互調用，可能會使性能變差，甚至產生無限迴圈。此類設計所產生的問題與單個遞歸過程所產生的問題相同，但更難檢測和調試。
調用時使用括弧。當Function過程以遞歸方式調用它自身時，您必須在過程名稱後加上括弧（即使不存在參數列表）。否則，函數名就會被視為表示函數的返回值。
測試。在編寫遞歸過程時，應非常細心地進行測試，以確保它總是能滿足某些限制條件。您還應該確保不會因為過多的遞歸調用而耗盡記憶體。
