引言

“遞歸” 一詞是比較專業(yè)的計算機術語，在現(xiàn)實生活中，有一個更可愛的詞——“套娃”。如果把“遞歸算法”叫做“套娃算法”，或許可以減少一些恐懼程度。

套娃是有限的，同樣，遞歸也是有限的，這和我們經(jīng)常在影視作品中看到的“無限嵌套循環(huán)”是有很大區(qū)別的，遞歸一定存在某個可以返回的節(jié)點或條件，否則就會出現(xiàn)棧溢出錯誤（StackOverflowError）。

其實“套娃”這個詞已經(jīng)足以概括遞歸算法的本質(zhì)，就是函數(shù)本身調(diào)用自身，直到找到一個可以返回的條件，再層層返回。參考《盜夢空間》《明日邊緣》等。

遞歸算法一定可以改寫成非遞歸的實現(xiàn)方式（迭代）。本篇博客將會展示一個簡單的遞歸算法案例，并介紹評估遞歸算法時間復雜度的?Master公式。

一、案例：數(shù)組中的最大值

正如前面所說，遞歸算法一定可以改寫成迭代方式，那么也就是說，遞歸也屬于迭代，只不過它每次迭代的內(nèi)容，和上一次都是一致的。

假設一個數(shù)組，如何用遞歸的方式找到其中的最大值？

分析，我們可以使用一個類似二分的思路，將數(shù)組層層二分，左側(cè)找一個值，右側(cè)找一個值，二者取一個最大。反復這樣的過程。

完整代碼：

public class RecursionGetMax {public static int getMax(int[] arr, int L, int R) {if (arr == null || arr.length == 0)throw new IllegalArgumentException("參數(shù)異常");if (arr.length == 1)return arr[0];// arr[L..R]范圍上只有一個數(shù)，直接返回，base caseif (L == R)return arr[L];// 2個元素以上int mid = L + ((R - L) >> 1);// 遞歸取得區(qū)域最大int leftMax = getMax(arr, L, mid);int rightMax = getMax(arr, mid + 1, R);return Math.max(leftMax, rightMax);}public static void main(String[] args) {int[] arr = {1, 2, 3, 5, 22, 5, 221, 4, 6, 43, 6, 21, 1, 3, 3, 9};int max = getMax(arr, 0, arr.length - 1);System.out.println(max);} }

注意，這道題在設計時，我們首先要有二分是思路基礎，然后我們思考，要設計這樣一個函數(shù)，這個函數(shù)一定會接收一個需要查找的數(shù)組，而僅僅傳遞數(shù)組的話，那么就需要在方法中反復拷貝新數(shù)組，顯然空間復雜度太高，因此，不妨提供額外的兩個指針，方便我們選取數(shù)組上的數(shù)，這樣每次傳遞指針的值，就可以避免每次傳遞截取的數(shù)組。

其次，基礎條件也是關鍵，base case 是可以直接返回的條件，即當 L == R 時，代表我們已經(jīng)無法再繼續(xù)二分，因此可以直接返回，這就是最終的返回節(jié)點，如果沒有這個條件，那么遞歸將持續(xù)執(zhí)行下去，直到 StackOverflow 。因此，在設計遞歸方法的時候，一定要考慮好 base case。

二、遞歸的底層執(zhí)行與邏輯分析方式

2.1 遞歸的底層實現(xiàn)

在系統(tǒng)中，遞歸的實現(xiàn)是使用一個系統(tǒng)棧來完成的，當方法執(zhí)行到自身調(diào)用時，系統(tǒng)會將“現(xiàn)場”保存到系統(tǒng)棧中，擦除局部變量，再重新跳到函數(shù)的開頭繼續(xù)執(zhí)行。

例如，一個數(shù)組 arr = {4, 3, 8, 5, 7}，初始 L = 0，R = 4，leftMax的返回值調(diào)用過程：

2.2 邏輯分析方式

對于一個希望使用遞歸實現(xiàn)的方法，我們并不需要每次都畫出類似上圖的棧結(jié)構來詳細分析，只需要畫出邏輯遞歸圖即可:

例如，arr = {5, 3, 4, 9}，初始 L = 0， R = 3：

三、遞歸算法的時間復雜度分析

由于遞歸算法是建立在一種不確定循環(huán)次數(shù)的情況下，有點類似 do-while 循環(huán)，因此，在分析遞歸算法復雜度形式的時候，只展開第一層的規(guī)模。

例如，上述二分取值的方式，就可以寫成這樣的時間消耗形式：

T(N) = a * T(N/b) + T(N^d)，其中 a，b，d 都是常數(shù)

具體的值就是：T(N) = 2?* T(N/2) + O(1) ，a = 2, b = 2, d = 0。

Master 公式，可以直接確定形如上面時間消耗形式的時間復雜度：

如果 logb a < d，復雜度為：O(N^d)

如果 logb a > d，復雜度為：O(N^(logb a))

如果?logb a == d，復雜度為：O(N^d * logN)

其中，logb a，指的是以b為底 a 的對數(shù)。案例中的問題，由于log2 > d ，1 >0 ，因此時間復雜度就是 O(N^log2) = O(N) 。

總結(jié)

以上是生活随笔為你收集整理的递归算法及其时间复杂度分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。