-
遞歸過程
鎖定
- 中文名
- 遞歸過程
- 外文名
- recursive process
- 實 質
- 直接調用系列過程語句間接過程
- 地 位
- 程序設計中一個強有力的工具
- 基本原理
- 重複的把原問題轉換為相似的問題
- 應用領域
- 計算機
遞歸過程簡單介紹
一個直接調用自己或通過一系列的過程調用語句間接調用自己的過程,稱作遞歸過程。它的基本原理是重複的把原問題轉換為相似的新問題,直到把問題解決為止。
“遞歸”過程是指調用自身的過程。通常,這不是編寫VisualBasic代碼的最有效方法。
其一,有很多數學函數是遞歸定義的,如大家熟悉的階乘函數
若
若
階Fibonacci數列
若n=0,
若n=1,
其它情形和ackerman函數
其它情形等;
其二,有的數據結構,如二叉樹,廣義表等,由於結構本身固有的遞歸特性,則它們的操作可遞歸地描述;
其三,還有一類問題,雖則問題本身沒有明顯的遞歸結構,用遞歸求解比迭代求解更簡單,如八皇后問題,Hanio塔問題等。
遞歸過程設計需要
1.當一個過程的運行期間調用另一個過程時,在執行被調用過程之前,系統需先完成如下三件事:
(1)將所有的實在參數,返回地址等信息傳遞給被調用的過程保存;
(2)為被調用過程的局部變量分配存儲空間;
(3)將控制轉移到被調用入口。
2.從被調過程返回調用過程時,需要:
(1)保存被調用過程的計算結果;
(2)釋放被調用過程的數據區;
(3)依照被調過程保存的返回地址將控制轉移到調用過程,服從後調用先返回的原則。
3.在設計過程中,我們需要注意的關鍵點是:
(1)用較簡單的問題來表示較複雜的問題;
遞歸過程注意事項
1.限制條件
在設計一個遞歸過程時,必須至少測試一個可以終止此遞歸的條件,並且還必須對在合理的遞歸調用次數內未滿足此類條件的情況進行處理。如果沒有一個在正常情況下可以滿足的條件,則過程將陷入執行無限循環的高度危險之中。
2.內存使用
3.效率
幾乎在任何情況下都可以用循環替代遞歸。循環不會產生傳遞變量、初始化附加存儲空間和返回值所需的開銷,因此使用循環相對於使用遞歸調用可以大幅提高性能。
4.相互遞歸
如果兩個過程相互調用,可能會使性能變差,甚至產生無限循環。此類設計所產生的問題與單個遞歸過程所產生的問題相同,但更難檢測和調試。
5.調用時使用括號
6.測試
在編寫遞歸過程時,應非常細心地進行測試,以確保它總是能滿足某些限制條件。您還應該確保不會因為過多的遞歸調用而耗盡內存。
- 參考資料
-
- 1. 08.棧(二)棧的應用 .CSDN博客[引用日期2017-12-23]
- 2. 棧與遞歸過程 .chinaunix博客[引用日期2017-12-23]