每談到遞歸，我們總會免不了聯(lián)系到斐波那契(Fibonacci)數(shù)列，當(dāng)然也不可忽視，斐波那契數(shù)列確實(shí)是一個很好的例子。但在現(xiàn)實(shí)當(dāng)中，我們只有在迫不得已的情況下才使用遞歸，因?yàn)檫f歸本身的效率并不理想，但他的思想?yún)s值得我們留存在記憶之中。

題目一：寫一個函數(shù)，輸入n，求斐波那契數(shù)列的第n項。

我們先一起看一下該題目的遞歸實(shí)現(xiàn)，從而學(xué)會寫遞歸的三要素：

//第一要素：明確你這個函數(shù)想要干什么
//函數(shù)功能：計算斐波那契數(shù)列的第n項
long long Fibonacci(unsigned int n)
{
    //第二要素：尋找遞歸結(jié)束條件
    if( n <= 1)
        return i == 0 ? 0 : 1;
    //第三要素：找出函數(shù)的等價關(guān)系式
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

但在面試的時候，面試官可不會輕易放過你，他會覺著上面的遞歸實(shí)現(xiàn)效率太低，原因在于我們在求斐波那契數(shù)列第n項的時候，中間計算了很多重復(fù)項，而且是不必要的計算，如下圖的遞歸樹：

改進(jìn)的方法并不復(fù)雜，那就是直接使用迭代的方式進(jìn)行處理，避免重復(fù)計算就可以了。

long long Fibonacci(unsigned int n)
{
    int result[2] = {0,1};
    if(n < 2)
        return result[n];
    
    long long fibNumOne = 1;
    long long fibNumTwo = 0;
    long long fibN = 0;
    for(int i = 2; i <= n; i++){
    fibN = fibNumOne + fibNumTwo;
        
        fibNumTwo = fibNumOne;
        fibNumOne = fibN;
    }
    
    return fibN;
}

在高級語言中，函數(shù)自己調(diào)用和調(diào)用其他函數(shù)并沒有本質(zhì)的不同。我們把一個直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù)，稱作遞歸函數(shù)。

不過，寫遞歸程序最怕的就是陷入永不結(jié)束的無窮遞歸中。切記，每個遞歸定義必須至少有一個終止條件，當(dāng)滿足這個條件時遞歸不再進(jìn)行，即函數(shù)不再調(diào)用自身而是返回值。

對比了上面所提到的兩種實(shí)現(xiàn)斐波那契的代碼，迭代和遞歸的區(qū)別是：迭代使用的是循環(huán)結(jié)構(gòu)，遞歸使用的是選擇結(jié)構(gòu)。

使用遞歸能使程序的結(jié)構(gòu)更清晰、更簡潔、更容易讓人理解，從而減少讀懂代碼的時間。

但大量的遞歸調(diào)用會建立函數(shù)的副本，會消耗大量的時間和內(nèi)存，而迭代則不需要此種代價。

遞歸函數(shù)分為調(diào)用和回退階段，遞歸的回退順序是它調(diào)用順序的逆序。

今日主要介紹遞歸，關(guān)于迭代只是簡要提及，防止大家面試時避免失誤。后面幾個例子都是關(guān)于遞歸實(shí)現(xiàn)。

題目二：寫一個函數(shù)，輸入n，求n的階乘n!。

//第一要素：明確你這個函數(shù)想要干什么
//函數(shù)功能：計算n的階乘
long long f(unsigned int n)
{
    //第二要素：尋找遞歸結(jié)束條件
    if( n <= 2)
        return n;
    //第三要素：找出函數(shù)的等價關(guān)系式
    return n * f(n - 1);
}

//第一要素：明確你這個函數(shù)想要干什么
//函數(shù)功能：計算青蛙跳上一個n級的臺階總共有多少種跳法
long long jump(unsigned int n)
{
    //第二要素：尋找遞歸結(jié)束條件
    if( n <= 2)
        return n;
    //第三要素：找出函數(shù)的等價關(guān)系式
    return jump(n - 1) + jump(n - 2);
}

一定要注意遞歸結(jié)束條件是否夠嚴(yán)謹(jǐn)問題，有很多人在使用遞歸的時候，由于結(jié)束條件不夠嚴(yán)謹(jǐn)，導(dǎo)致出現(xiàn)死循環(huán)。所以，當(dāng)我們在第二步找出了一個遞歸結(jié)束條件的時候，可以把結(jié)束條件寫進(jìn)代碼，然后進(jìn)行第三步，但是請注意，當(dāng)我們第三步找出等價函數(shù)之后，還得再返回去第二步，根據(jù)第三步函數(shù)的調(diào)用關(guān)系，判斷會不會出現(xiàn)一些漏掉的結(jié)束條件，并進(jìn)行查漏補(bǔ)缺。

題目四：編寫一個遞歸函數(shù)，實(shí)現(xiàn)將輸入的任意長度的字符串反向輸出的功能。

要將一個字符串反向地輸出，小禹禹們一般采用的方法是將該字符串存放到一個數(shù)組中，然后將數(shù)組元素反向的輸出即可。這道題要求輸入是任意長度，所以使用遞歸會比較容易解決。

我們說過，遞歸三要素的第二要素是需要有一個結(jié)束的條件，那么我們可將“#”作為一個輸入結(jié)束的條件。

//第一要素：明確你這個函數(shù)想要干什么
//函數(shù)功能：將輸入的任意長度的字符串反向輸出
void print()
{
    char a;
    scanf("%c", &a);

    //第三要素：找出函數(shù)的等價關(guān)系式
    if( a != '#') print();
    //第二要素：尋找遞歸結(jié)束條件，#表示遞歸結(jié)束，進(jìn)行返回輸出。
    if( a != '#') printf( "%c", a);
}

假設(shè)我們從屏幕上輸入字符串：ABCDE#

分而治之的思想古已有之，秦滅六國，統(tǒng)一天下正是采取各個擊破、分而治之的原則。

而分治思想在算法設(shè)計中也是非常常見的，當(dāng)一個問題規(guī)模較大且不易求解的時候，就可以考慮將問題分成幾個小的模塊，逐一解決（這種思想在以后的工作更是深有體會，處世之道）。

分治思想和遞歸就像是親兄弟的關(guān)系，因?yàn)椴捎梅种嗡枷胩幚韱栴}，其各個小模塊通常具有與大問題相同的結(jié)構(gòu)，這種特性也使遞歸技術(shù)有了用武之地。我們接下來以折半查找來講解分治思想。

折半查找法是一種常用的查找方法，該方法通過不斷縮小一半的查找范圍，直到達(dá)到目的，所以效率比較高。

線性檢索和二分檢索求 1 的位置：

背景：一位法國數(shù)學(xué)家曾編寫過一個印度的古老傳說：在世界中心貝納勒斯的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。

僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

這其實(shí)也是一個經(jīng)典的遞歸問題。我們可以做這樣的考慮：

• 先將前63個盤子移動到Y(jié)上，確保大盤在小盤下。

• 再將最底下的第64個盤子移動到Z上。

• 最后將Y上的63個盤子移動到Z上。

接下來，我們要做的就是將Y上的前62個盤子借助Z移動到X上，再將最底下的第63個盤子移動到Z上，后面就是重復(fù)這一操作，直到剩一個盤子是，直接將該盤子由X移動到Z。

景禹給你說了，可能還是有點(diǎn)點(diǎn)朦朧，沒關(guān)系，回頭你在玩一玩這個游戲，你就知道如何操作了。給大家分享的《數(shù)據(jù)結(jié)構(gòu)與算法》第三十三講遞歸和分治思想3中有這個有游戲。

題目五：編程實(shí)現(xiàn)漢諾塔的移動過程。

#include <stdio.h>
//第一要素：明確你這個函數(shù)想要干什么
// 函數(shù)功能：將 n 個盤子從 x 借助 y 移動到 z
void move(int n, char x, char y, char z)
{
    //第二要素：尋找遞歸結(jié)束條件，當(dāng)n=1時，直接將盤子從x移動到z
  if( 1 == n )
  {
    printf("%c-->%c\n", x, z);
  }
  else
  {
        //第三要素：找出函數(shù)的等價關(guān)系式，并不考慮具體的移動過程，僅考慮完成任務(wù)
    move(n-1, x, z, y); // 將 n-1 個盤子從x借助z移到y(tǒng)上
    printf("%c-->%c\n", x, z);// 將第n個盤子從x移到z上
    move(n-1, y, x, z); // 將 n-1 個盤子從y借助x移到z上
  }
}

int main()
{
  int n;

  printf("請輸入漢諾塔的層數(shù): ");
  scanf("%d", &n);
  printf("移動的步驟如下: \n");
  move(n, 'X', 'Y', 'Z');

  return 0;
}

今日與小禹禹們分享遞歸與分治思想就到這里啦！