對于很多人來說，都知道遞歸，也能看的懂遞歸，但在實際項目過程中，卻不知道如何使用遞歸，這裡給遞歸做個總結。

在數學與計算機科學中，遞歸(Recursion)是指在函數的定義中使用函數自身的方法。實際上，遞歸，顧名思義，其包含了兩個意思：遞和歸，這正是遞歸思想的精華所在。

通俗點講，我們可以把” 遞歸 “比喻成 “查字典 “，當你查一個詞，發現這個詞的解釋中某個詞仍然不懂，于是你開始查這第二個詞。

可惜，第二個詞裡仍然有不懂的詞，于是查第三個詞，這樣查下去，直到有一個詞的解釋是你完全能看懂的，那麼遞歸走到了盡頭，然後你開始後退，逐個明白之前查過的每一個詞，最終，你明白了最開始那個詞的意思。

遞歸就是有去（遞去）有回（歸來），如下圖所示。“有去”是指：遞歸問題必須可以分解為若幹個規模較小，與原問題形式相同的子問題，這些子問題可以用相同的解題思路來解決，就像上面例子中的鑰匙可以打開後面所有門上的鎖一樣；“有回”是指 : 這些問題的演化過程是一個從大到小，由近及遠的過程，并且會有一個明确的終點(臨界點)，一旦到達了這個臨界點，就不用再往更小、更遠的地方走下去。最後，從這個臨界點開始，原路返回到原點，原問題解決。

• 明确遞歸終止條件;
• 給出遞歸終止時的處理辦法;
• 提取重複的邏輯，縮小問題規模;

我們知道，遞歸就是有去有回，既然這樣，那麼必然應該有一個明确的臨界點，程序一旦到達了這個臨界點，就不用繼續往下遞去而是開始實實在在的歸來。換句話說，該臨界點就是一種簡單情境，可以防止無限遞歸。

我們剛剛說到，在遞歸的臨界點存在一種簡單情境，在這種簡單情境下，我們應該直接給出問題的解決方案。一般地，在這種情境下，問題的解決方案是直觀的、容易的。

我們在闡述遞歸思想内涵時談到，遞歸問題必須可以分解為若幹個規模較小、與原問題形式相同的子問題，這些子問題可以用相同的解題思路來解決。從程序實現的角度而言，我們需要抽象出一個幹淨利落的重複的邏輯，以便使用相同的方式解決子問題。

下面總結一下常見的遞歸問題和實現算法。

斐波那契數列的排列是：0，1，1，2，3，5，8，13，21，34，55，89，144……依次類推下去，你會發現，它後一個數等于前面兩個數的和。在這個數列中的數字，就被稱為斐波那契數。

遞歸思想：一個數等于前兩個數的和。

首先分析數列的遞歸表達式：

代碼如下:

/** * 斐波那契數列的遞歸寫法 * @param n * @return */ long F(int n){ if (n<=1) return n; return F(n-1) F(n-2); }

可以看到，遞歸寫法簡單優美，省去考慮很多邊界條件的時間。當然，遞歸算法會保存很多的臨時數據，類似于堆棧的過程，如果棧深太深，就會造成内存用盡，程序崩潰的現象。

遞歸思想：n! = n * (n-1)!

首先分析數列的遞歸表達式：

代碼如下:

long factorial(int n){ if (n <=1) return 1; return j(n-1)*n; }

例如給出正整數 n=12345，希望以各位數的逆序形式輸出，即輸出54321。

遞歸思想：首先輸出這個數的個位數，然後再輸出前面數字的個位數，直到之前沒數字。

首先分析數列的遞歸表達式：

代碼如下:

/** * 倒序輸出正整數的各位數 * @param n */ void printDigit(int n){ System.out.print(n); if (n > 10){ printDigit(n/10); } }

數學描述就是：

有三根杆子X，Y，Z。X杆上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則将所有圓盤移至Y杆：

1. 每次隻能移動一個圓盤；
2. 大盤不能疊在小盤上面。

遞歸思想：

1. 将X杆上的n-1個圓盤都移到空閑的Z杆上，并且滿足上面的所有條件
2. 将X杆上的第n個圓盤移到Y上
3. 剩下問題就是将Z杆上的n-1個圓盤移動到Y上了

公式描述有點麻煩，用語言描述下吧：

1. 以Y杆為中介，将前n-1個圓盤從X杆挪到Z杆上(本身就是一個n-1的漢諾塔問題了！)
2. 将第n個圓盤移動到Y杆上
3. 以X杆為中介，将Z杆上的n-1個圓盤移到Y杆上(本身就是一個n-1的漢諾塔問題了！)

代碼如下：

/** * 漢諾塔 * 有柱子 x z y，最終将x上的n個圓盤借助z移動到y上 * 遞歸思想： * 1.将x上的n-1個放入到z上，借助y * 2.将x上的n圓盤放到y上 * 3.将z上的n-1個圓盤放入y * @param n * @param from * @param tmp * @param to */ void hanoi(int n,char from,char tmp,char to){ if (n>0) { hanoi(n - 1, from, to, tmp); System.out.println("take " n " from " from " to " to); hanoi(n - 1, tmp, from, to); } }

還是拿斐波那契數列來做例子：

long Fib(int n){ if (n<=1) return n; return Fib(n-1) Fib(n-2); }

這段代碼應該算是短小精悍（執行代碼隻有一行），直觀清晰，而且非常符合許多程序員的代碼美學，是如果用這段代碼試試計算Fib(1000)我想就再也爽不起來了，它的運行時間也許會讓你抓狂。

看來好看的代碼未必中用，如果程序在效率不能接受那美觀神馬的就都是浮雲了。如果簡單分析一下程序的執行流，就會發現問題在哪，以計算Fibonacci(5)為例：

從上圖可以看出，在計算Fib(5)的過程中，Fib(1)計算了兩次、Fib(2)計算了3次，Fib(3)計算了兩次，本來隻需要5次計算就可以完成的任務卻計算了9次。這個問題随着規模的增加會愈發凸顯，以至于Fib(1000)已經無法再可接受的時間内算出。

我們當時使用的是簡單的用定義來求 fib(n)，也就是使用公式 fib(n) = fib(n-1) fib(n-2)。這樣的想法是很容易想到的，可是仔細分析一下我們發現，當調用fib(n-1)的時候，還要調用fib(n-2)，也就是說fib(n-2)調用了兩次，同樣的道理，調用f(n-2)時f(n-3)也調用了兩次，而這些冗餘的調用是完全沒有必要的。可以計算這個算法的複雜度是指數級的。

由以上分析我們可以看到，遞歸在處理問題時要反複調用函數，這增大了它的空間和時間開銷，所以在使用疊代可以很容易解決的問題中，使用遞歸雖然可以簡化思維過程，但效率上并不合算。效率和開銷問題是遞歸最大的缺點。

雖然有這樣的缺點，但是遞歸的力量仍然是巨大而不可忽視的，因為有些問題使用疊代算法是很難甚至無法解決的。這時遞歸的作用就顯示出來了。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!