讀完這篇算法總結(jié)，我感覺自己距離谷歌更近了

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

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

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

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

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

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

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;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 再將最底下的第64個(gè)盤子移動(dòng)到Z上。

• 最后將Y上的63個(gè)盤子移動(dòng)到Z上。

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

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

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

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

int main()
{
  int n;

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

  return 0;
}

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