一、什么是遞歸
很多數(shù)據(jù)結(jié)構(gòu)的定義都是根據(jù)遞歸性質(zhì)來進行定義的，是因為這些結(jié)構(gòu)固有的性質(zhì)。遞歸是指某個函數(shù)直接或間接的調(diào)用自身。問題的求解過程就是劃分成許多相同性質(zhì)的子問題的求解，而小問題的求解過程可以很容易的求出，這些子問題的解就構(gòu)成里原問題的解了。
二、遞歸的幾個特點
1.遞歸式，就是如何將原問題劃分成子問題。
2.遞歸出口，遞歸終止的條件，即最小子問題的求解，可以允許多個出口。
3.界函數(shù)，問題規(guī)模變化的函數(shù)，它保證遞歸的規(guī)模向出口條件靠攏
三、遞歸的運做機制
很明顯，很多問題本身固有的性質(zhì)就決定此類問題是遞歸定義，所以遞歸程序很直接算法程序結(jié)構(gòu)清晰、思路明了。但是遞歸的執(zhí)行過程卻很讓人費解，這也是讓很多人難理解遞歸的原因之一。由于遞歸調(diào)用是對函數(shù)自身的調(diào)用，在一次調(diào)用沒有結(jié)束之前又開始了另外一次調(diào)用，按照作用域的規(guī)定，函數(shù)在執(zhí)行終止之前是不能收回所占用的空間，必須保存下來，這也就意味著每一次的調(diào)用都要把分配的相應(yīng)空間保存起來。為了更好管理這些空間，系統(tǒng)內(nèi)部設(shè)置一個棧，用于存放每次函數(shù)調(diào)用與返回所需的各種數(shù)據(jù)，其中主要包括函數(shù)的調(diào)用結(jié)束的返回地址，返回值，參數(shù)和局部變量等。
其過程大致如下：
1.計算當前函數(shù)的實參的值
2.分配空間，并將首地址壓棧，保護現(xiàn)場
3.轉(zhuǎn)到函數(shù)體，執(zhí)行各語句，此前部分會重復發(fā)生(遞歸調(diào)用)
4.直到出口，從棧頂取出相應(yīng)數(shù)據(jù)，包括，返回地址，返回值等等，收回空間，恢復現(xiàn)場，轉(zhuǎn)到上一層的調(diào)用位置繼續(xù)執(zhí)行本次調(diào)用未完成的語句。
四、引入非遞歸
從用戶使用角度來說，遞歸真的很簡便，對程序宏觀上容易理解。遞歸程序的時間復雜度雖然可以根據(jù)T(n)=T(n-1)*f(n)遞歸求出，其中f(n)是遞歸式的執(zhí)行時間復雜度，一般來說，時間復雜度和對應(yīng)的非遞歸差不多，但是遞歸的效率是相當?shù)偷乃饕l(fā)費在反復的進棧出棧，各種中斷等機制上(具體的可以參考操作系統(tǒng))更有甚者，在遞歸求解過程中，某些解會重復的求好幾次，這是不能容忍的，這些也是引入非遞歸機制的原因之一。
五、遞歸轉(zhuǎn)非遞歸的兩種方法
1.一般根據(jù)是否需要回朔可以把遞歸分成簡單遞歸和復雜遞歸，簡單遞歸一般就是根據(jù)遞歸式來找出遞推公式(這也就引申出分治思想和動態(tài)規(guī)劃)。而復雜遞歸一般就是模擬系統(tǒng)處理遞歸的機制，使用?；蜿犃械葦?shù)據(jù)結(jié)構(gòu)保存回朔點來求解。
很多數(shù)據(jù)結(jié)構(gòu)的定義都是根據(jù)遞歸性質(zhì)來進行定義的，是因為這些結(jié)構(gòu)固有的性質(zhì)。遞歸是指某個函數(shù)直接或間接的調(diào)用自身。問題的求解過程就是劃分成許多相同性質(zhì)的子問題的求解，而小問題的求解過程可以很容易的求出，這些子問題的解就構(gòu)成里原問題的解了。
二、遞歸的幾個特點
1.遞歸式，就是如何將原問題劃分成子問題。
2.遞歸出口，遞歸終止的條件，即最小子問題的求解，可以允許多個出口。
3.界函數(shù)，問題規(guī)模變化的函數(shù)，它保證遞歸的規(guī)模向出口條件靠攏
三、遞歸的運做機制
很明顯，很多問題本身固有的性質(zhì)就決定此類問題是遞歸定義，所以遞歸程序很直接算法程序結(jié)構(gòu)清晰、思路明了。但是遞歸的執(zhí)行過程卻很讓人費解，這也是讓很多人難理解遞歸的原因之一。由于遞歸調(diào)用是對函數(shù)自身的調(diào)用，在一次調(diào)用沒有結(jié)束之前又開始了另外一次調(diào)用，按照作用域的規(guī)定，函數(shù)在執(zhí)行終止之前是不能收回所占用的空間，必須保存下來，這也就意味著每一次的調(diào)用都要把分配的相應(yīng)空間保存起來。為了更好管理這些空間，系統(tǒng)內(nèi)部設(shè)置一個棧，用于存放每次函數(shù)調(diào)用與返回所需的各種數(shù)據(jù)，其中主要包括函數(shù)的調(diào)用結(jié)束的返回地址，返回值，參數(shù)和局部變量等。
其過程大致如下：
1.計算當前函數(shù)的實參的值
2.分配空間，并將首地址壓棧，保護現(xiàn)場
3.轉(zhuǎn)到函數(shù)體，執(zhí)行各語句，此前部分會重復發(fā)生(遞歸調(diào)用)
4.直到出口，從棧頂取出相應(yīng)數(shù)據(jù)，包括，返回地址，返回值等等，收回空間，恢復現(xiàn)場，轉(zhuǎn)到上一層的調(diào)用位置繼續(xù)執(zhí)行本次調(diào)用未完成的語句。
四、引入非遞歸
從用戶使用角度來說，遞歸真的很簡便，對程序宏觀上容易理解。遞歸程序的時間復雜度雖然可以根據(jù)T(n)=T(n-1)*f(n)遞歸求出，其中f(n)是遞歸式的執(zhí)行時間復雜度，一般來說，時間復雜度和對應(yīng)的非遞歸差不多，但是遞歸的效率是相當?shù)偷乃饕l(fā)費在反復的進棧出棧，各種中斷等機制上(具體的可以參考操作系統(tǒng))更有甚者，在遞歸求解過程中，某些解會重復的求好幾次，這是不能容忍的，這些也是引入非遞歸機制的原因之一。
五、遞歸轉(zhuǎn)非遞歸的兩種方法
1.一般根據(jù)是否需要回朔可以把遞歸分成簡單遞歸和復雜遞歸，簡單遞歸一般就是根據(jù)遞歸式來找出遞推公式(這也就引申出分治思想和動態(tài)規(guī)劃)。而復雜遞歸一般就是模擬系統(tǒng)處理遞歸的機制，使用?；蜿犃械葦?shù)據(jù)結(jié)構(gòu)保存回朔點來求解。