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