遞歸到底是個啥？

常聽見的一句話就是：自己調用自己。

按照這個說法，寫個簡單的遞歸自己推導一下的確可以，但是總是有點繞，推著推著自己把自己陷進去了。

遞歸函數運行時，實際上會進行一個壓棧(思考棧的特點，先進后出，后進先出)的過程。

寫個簡單的遞歸排序算法：

public static voidmain(String[] args) {int[] arr={1,3,4,2};

System.out.println(digui(arr,0,arr.length-1));

}public static int digui(int[] arr,int L,intR){if(L==R)returnarr[L];int mid=(L+R)/2;int LeftMax=digui(arr,L,mid);int RightMax=digui(arr,mid+1,R);returnMath.max(LeftMax,RightMax);

}

當第一次進入digui方法時，在第十行，也就是

int LeftMax=digui(arr,L,mid);

1.程序會第一次進入到子方法，也就是調用本身。這時候會往堆棧里面記錄此時這個方法的信息，比如L=0，R=3,mid=1等等,并且暫停這個方法的繼續運行，先進入到子方法。

2.程序進入子方法，第二次到第十行代碼時，依舊會往堆棧里記錄此時的方法信息，L=0，R=1,mid=0等等

3.程序再次進入子方法，第三次運行到第十行代碼時，此時L=0，R=0。所以會返回arr[0],也就是1.因為返回了數值，沒有再次調用自己，所以不用再次壓棧

此時的堆棧信息如圖

4.由于上一步返回了一個1，那么自然就會先回到其父方法，也就是L=0，R=1,mid=0的這個方法。這時候LeftMax就會接受到其子方法的返回的數據，也就是1.

5.接著運行第十一行代碼，繼續壓棧，然后運行其子方法。自己捋一下，第十一行的子方法返回的是3

6.接著運行第十二行代碼，會比較1和3誰大，然后返回。至此，L=0，R=1,mid=0時的這個方法徹底執行完畢，接著就會執行出棧操作。

有了堆棧圖的輔助，理清遞歸過程就清晰多了。大家可以自己捋一捋接下來幾步的過程。總比以前光憑一個腦袋想好多了。

遞歸的時間復雜度怎么算？

一般情況下，可以用以下公式：

T(N)=aT(N/b)+O(N^d);

其中，T是樣本，N的樣本量。

b代表這個樣本被分為了幾部分(上面的算法被分為兩部分(L+R)/2，所以b=2)，a代表運行了多少次(上面的算法需要調用自己兩次，所以a=2)。

一定要記住，這個a和b，不需要展開所有堆棧里的情況，只需要看最表面上的代碼就行，不用想里面的子方法還調用了多少次本身。

后面接著的O(N^d)代表除了前面那部分主體外，還需要多少時間復雜度，比如前面的aT(N/b)這部分運行完，我還需要O(N^2)的時間復雜度才能最終完成輸出，那么d=2。

那么T(N)=aT(N/b)+O(N^d)到底怎么求出具體結果呢？

上面的算法中，a=2,b=2,d=0

所以log(b,a)=1.大于d的。所以時間復雜度為O(N)

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的java 递归 时间复杂度_递归到底是怎么实现的?它的时间复杂度怎么算？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。