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