java遞歸

遞歸：一個過程（方法）直接或間接的調用自己本身，這個過程叫做遞歸。

例如這樣一個小程式：

這個程式中，類demo5中的test方法裡邊又調用了test方法本身，這就是遞歸。在main方法中運作的時候，當參數是3時，輸出的num結果是6；參數是4時，結果是24；參數是5時，結果是120.

這些結果得來的過程是這樣的：

1.當參數是3時，也就是int num=demo.test(3)；這個時候會進入到test方法中，首先經過if判斷a！=1，是以直接走下一步，也就是result=test(3-1)*3,即result=test（2）*3；

因為這裡又有test方法，參數是2，是以會在這裡再次調用test方法，下一步再if判斷，依舊是a！=1，則test（2）的結果就是test（1）*2；

那麼上一步中result=test（2）*3中的test（2）就要進行替換，結果是result=test(1)*2*3；

走到這一步以後，程式并沒有結束，因為這裡邊依舊還有test方法，那麼會再次調用test，再次if判斷，這時候a==1，則return 1；也就是test（1）=1；

那麼，上邊的結果将會再次變化,即：num=result=test（1）*2*3=1*2*3=6。這就是當參數是3的時候，結果是6的遞歸運作過程。

2.同樣的，當參數是4的時候，也就是int num=demo.test(4)；首先a！=1，那麼運作到下一步就是result=test（3）*4；緊接着，test（3）之後的運作步驟就和參數是3的時候一樣，那麼最終的結果就是：num=result=test（3）*4=1*2*3*4=24；

3.那麼當參數是5的時候，按照上邊的步驟，也就是将會在最開始的時候程式設計test（4）*5，那麼結果就是24*5=120.

再例如下邊的求累加和的例子：

這個例子是求比我們指定的正整數小的所有正整數的和，在demo11類中的test方法中又調用了test方法本身，這裡用到了遞歸。

在這個例子中，參數是3的時候，結果是6；參數是4的時候，結果是10；參數是5的時候，結果是15。它的具體實作過程是這樣的：

1.當參數是3的時候，也就是n=3，首先if判斷n>0,那麼sum=3+test（2）；緊接着test（2）再次if判斷n>0,結果是2+test（1）；那麼整個sum結果就會變成sum=3+test(2)=3+2+test(1)；

再然後，繼續test（1），結果是1+test（0）；再然後繼續test（0），n=0，return 0，結果是0；那麼整個sum的結果就是sum=3+2+1+0=6。

2.當參數是4的時候，n=4，同樣的，首先是sum=4+test（3），然後就是重複test（3）的步驟，結果是sum=4+test（3）=4+3+2+1+0=10。

3.再到參數是5的時候，n=5，那麼一開始if之後就是sum=5+test(4)；然後sum=5+4+3+2+1+0=15。

我們以前讀書的時候學過從1加到100的累加和，結果是5050，那麼在這裡如果把參數設為100，結果也是5050，是完全符合的，而計算的步驟也和上邊的一樣。

遞歸的過程實際上可以看成是不斷的調用不斷的替換的過程，有人認為遞歸的優點是：采用遞歸算法比采用疊代算法要更加清晰和簡單。

在編寫遞歸的時候，必須要使用if在遞歸調用不執行的時候強制方法傳回，否則程式将永遠不傳回。