什么是遞歸

遞歸在程序語言中簡單的理解是：方法自己調用自己。

特點：需要有結束調用條件，需要數據格式保持一致，數據嵌套層級不確定性。

優(yōu)點

- 節(jié)省代碼

- 符合編程思想，容易理解

**缺點：**

- 效率較低

- 遞歸層次太深，耗內存且容易棧溢出一定要使用的話，最好使用緩存避免相同的計算，限制遞歸調用的次數

程序調用自身的編程技巧稱為遞歸（ recursion）。遞歸作為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

1，采用遞歸方法的原因：

遞歸通常用來解決結構自相似的問題。所謂結構自相似，是指構成原問題的子問題與原問題在結構上相似，可以用類似的方法解決。具體地，整個問題的解決，可以分為兩部分：第一部分是一些特殊情況，有直接的解法；第二部分與原問題相似，但比原問題的規(guī)模小。實際上，遞歸是把一個不能或不好解決的大問題轉化為一個或幾個小問題，再把這些小問題進一步分解成更小的問題，直至每個小問題都可以直接解決。

2，遞歸的兩個基本要素：

邊界條件：確定遞歸到何時終止，也稱為遞歸出口。

遞歸模式：大問題是如何分解為小問題的，也稱為遞歸體。遞歸函數只有具備了這兩個要素，才能在有限次計算后得出結果

3.遞歸調用的執(zhí)行過程

（1）運動開始時，首先為遞歸調用建立一個工作棧，其結構包括值參、局部變量和返回地址；

（2）每次執(zhí)行遞歸調用之前，把遞歸函數的值參和局部變量的當前值以及調用后的返回地址壓棧；

（3）每次遞歸調用結束后，將棧頂元素出棧，使相應的值參和局部變量恢復為調用前的值，

然后轉向返回地址指定的位置繼續(xù)執(zhí)行。

遞歸算法的使用

public void recursiveTest(){

? ? recursiveTest();? //自己調用自己，就叫遞歸

}