一般定義（來(lái)自網(wǎng)絡(luò)）：在調(diào)用一個(gè)函數(shù)的過(guò)程中又出現(xiàn)直接或間接地調(diào)用該函數(shù)本身，就是函數(shù)的遞調(diào)用。

為求解規(guī)模為N的問(wèn)題，設(shè)法將它分解成規(guī)模較小的問(wèn)題，然后從這些小問(wèn)題的解方便地構(gòu)造出大問(wèn)題的解，并且這些規(guī)模較小的問(wèn)題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問(wèn)題，并從這些更小問(wèn)題的解構(gòu)造出規(guī)模較大問(wèn)題的解。特別地，當(dāng)規(guī)模N=1時(shí)，能直接得解。

遞歸算法的執(zhí)行過(guò)程分遞推和回歸兩個(gè)階段。
在遞推階段，把較復(fù)雜的問(wèn)題（規(guī)模為n）的求解推到比原問(wèn)題簡(jiǎn)單一些的問(wèn)題（規(guī)模小于n）的求解。
在回歸階段，當(dāng)獲得最簡(jiǎn)單情況的解后，逐級(jí)返回，依次得到稍復(fù)雜問(wèn)題的解。

在編寫遞歸函數(shù)時(shí)要注意，函數(shù)中的局部變量和參數(shù)知識(shí)局限于當(dāng)前調(diào)用層，當(dāng)遞推進(jìn)入“簡(jiǎn)單問(wèn)題”層時(shí)，原來(lái)層次上的參數(shù)和局部變量便被隱蔽起來(lái)。在一系列“簡(jiǎn)單問(wèn)題”層，它們各有自己的參數(shù)和局部變量。由于遞歸引起一系列的函數(shù)調(diào)用，并且可能會(huì)有一系列的重復(fù)計(jì)算，遞歸算法的執(zhí)行效率相對(duì)較低。
當(dāng)某個(gè)遞歸算法能較方便地轉(zhuǎn)換成遞推算法時(shí)，通常按遞推算法編寫程序。

總結(jié)一下：
1：遞歸算法的思想

遞歸算法是把問(wèn)題轉(zhuǎn)化為規(guī)模縮小了的同類問(wèn)題的子問(wèn)題。
然后遞歸調(diào)用函數(shù)（或過(guò)程）來(lái)表示問(wèn)題的解。
在C語(yǔ)言中的運(yùn)行堆棧為他的存在提供了很好的支持，過(guò)程一般是通過(guò)函數(shù)或子過(guò)程來(lái)實(shí)現(xiàn)。

遞歸算法：在函數(shù)或子過(guò)程的內(nèi)部，直接或者間接地調(diào)用自己的算法。

2：遞歸算法的特點(diǎn)：
遞歸算法是一種直接或者間接地調(diào)用自身算法的過(guò)程。
在計(jì)算機(jī)編寫程序中，遞歸算法對(duì)解決一大類問(wèn)題是十分有效的，它往往使算法的描述簡(jiǎn)潔而且易于理解。

遞歸算法解決問(wèn)題的特點(diǎn)：
(1) 遞歸就是在過(guò)程或函數(shù)里調(diào)用自身。
(2) 在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。
(3) 遞歸算法解題通常顯得很簡(jiǎn)潔，但遞歸算法解題的運(yùn)行效率較低。所以一般不提倡用遞歸算法設(shè)計(jì)程序。
(4) 在遞歸調(diào)用的過(guò)程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來(lái)存儲(chǔ)。遞歸次數(shù)過(guò)多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計(jì)程序。

3：遞歸算法的要求
遞歸算法所體現(xiàn)的“重復(fù)”一般有三個(gè)要求：

一是每次調(diào)用在規(guī)模上都有所縮小(通常是減半)；
二是相鄰兩次重復(fù)之間有緊密的聯(lián)系，前一次要為后一次做準(zhǔn)備(通常前一次的輸出就作為后一次的輸入)；
三是在問(wèn)題的規(guī)模極小時(shí)必須用直接給出解答而不再進(jìn)行遞歸調(diào)用，因而每次遞歸調(diào)用都是有條件的(以規(guī)模未達(dá)到直接解答的大小為條件)，無(wú)條件遞歸調(diào)用將會(huì)成為死循環(huán)而不能正常結(jié)束。

我們看看幾個(gè)經(jīng)典遞歸問(wèn)題

使用遞歸來(lái)解決斐波那契數(shù)列的第n個(gè)數(shù)是多少？（初始默認(rèn)前兩個(gè)值是 1,2）斐波那契數(shù)列簡(jiǎn)單來(lái)說(shuō)就是下一個(gè)數(shù)是前兩個(gè)數(shù)的總和。不知道這個(gè)的話請(qǐng)自行g(shù)oogle腦補(bǔ)一下。利用遞歸思想，可以寫成如下代碼

int is_recursive_fib(int index){
    if(index == 1 || index == 2){
        return index;
    }else{
        return is_recursive_fib(index - 1) + is_recursive_fib(index - 2 );
    }
}

當(dāng)index為 1 或者 2 的時(shí)候，就直接返回 index的值；
當(dāng)index不為 1 或者 2 的時(shí)候，就返回is_recursive_fib(index - 1) + is_recursive_fib(index - 2 )；

二話不說(shuō)，先上個(gè)小圖分析分析(畢竟沒(méi)有繪畫功底，見(jiàn)諒)

1.jpg

假設(shè)求第五個(gè)數(shù)，它的值是多少。
分析過(guò)程如下：

第一步，調(diào)用函數(shù) 傳遞參數(shù)是 5； 見(jiàn) ①
第二步，拆解為 f(4) + f(3)； 見(jiàn) ②
第三步，將左邊的f(4) 拆解為 f(3) + f(2)；見(jiàn) ③
第四步，將第三步分解出來(lái)f(3),再次拆分為 f(2) + f(1)； 見(jiàn) ④
這個(gè)時(shí)候根據(jù)返回條件 index 是 1 或者 2，就開始返回回去；
第五步，將f(2) + f(1) = 3的值返回回去； 見(jiàn)⑤
這個(gè)時(shí)候f(3)得到返回的值 3， 然后和f(2) 相加計(jì)算得到值 是 5
第六步，將f(3) + f(2)的值為 5， 返回給 f(4);見(jiàn) ⑥
這個(gè)時(shí)候 f(4)得到值 就是 5
第七步，拆解右邊的 f(3)為 f(2) + f(1); 見(jiàn) ⑦
這個(gè)時(shí)候 index為 1 和 2，滿足返回條件
第八步，將 f(2) + f(1)的值 為 3 返回給 f（3）；見(jiàn) ⑧
第九步，將左邊 f(4) 的值 5 和 右邊 f(3)的值 3 相加， 然后返回給 f（5）；見(jiàn)⑨
最后，我們就得到f(5)的結(jié)果是 8.

前面已經(jīng)提到使用遞歸，解決問(wèn)題思路上會(huì)很簡(jiǎn)單，但是效率卻非常低。
我們來(lái)改寫一下如果上面例子不用遞歸方法來(lái)實(shí)現(xiàn)，改用 for循環(huán)迭代計(jì)算看看效果如何。
先上代碼

int not_recursive_fib(int index){
    if(index == 1 || index == 2){
        return index;
    }

    int array[index+1];
    array[1] = 1;
    array[2] = 2;
    int i=0;
    for(i = 3;i<=index; i++){
        array = array[i-1] + array[i-2];
    }
    return array[index];
}

這個(gè)算法可以簡(jiǎn)單看出 如果是 1 或者 2 就直接返回了結(jié)果。
如果大于2的話， 怎定義一個(gè)數(shù)組， 在for 循環(huán)那里，每一次計(jì)算下一個(gè)值，下標(biāo)從3開始。
但是比較一下兩個(gè)的效率如何：
同一臺(tái)電腦設(shè)備前提下， 我們?cè)O(shè)置求第45個(gè)值是多少

2.png

相比之下，用遞歸方法的 比 不是用遞歸方法的效率居然差 5倍之多！ 本文章例子在CodeBlocks 13.12版本測(cè)試通過(guò)**recursion.c

給一道課外習(xí)題
漢諾（Hanoi）塔問(wèn)題：古代有一個(gè)梵塔，塔內(nèi)有三個(gè)座A、B、C，A座上有64個(gè)盤子，盤子大小不等，大的在下，小的在上（如圖）。有一個(gè)和尚想把這64個(gè)盤子從A座移到B座，但每次只能允許移動(dòng)一個(gè)盤子，并且在移動(dòng)過(guò)程中，3個(gè)座上的盤子始終保持大盤在下，小盤在上。在移動(dòng)過(guò)程中可以利用B座，要求打印移動(dòng)的步驟。如果只有一個(gè)盤子，則不需要利用B座，直接將盤子從A移動(dòng)到C。

3.gif

參考答案

/**
*
Tutorial 漢諾（Hanoi）塔問(wèn)題

show the steps how to move one by one

Author: hejing
Email: 2010jing@gmail.com
Date : 2015/11/3
*
**/

#include <stdio.h>

void move(char x,char y); // 對(duì)move函數(shù)的聲明
void hanoi(int n,char one,char two,char three) ;// 對(duì)hanoi函數(shù)的聲明
int count = -1;

int main()
{


    //hanoi函數(shù)
    int m;
    printf("請(qǐng)輸入一共有多少個(gè)板子需要移動(dòng):");
    scanf("%d",&m);
    printf("以下是%d個(gè)板子的移動(dòng)方案:\n",m);
    hanoi(m,'A','B','C');

    return 0;
}

// 定義hanoi函數(shù)
// 將n個(gè)盤從one座借助two座,移到three座
void hanoi(int n,char one,char two,char three) 
{

    if(n==1)
        move(one,three);
    else
    {
        hanoi(n-1,one,three,two); //首先把n-1個(gè)從one移動(dòng)到two
        move(one,three); //然后把最后一個(gè)n從one移動(dòng)到three
        hanoi(n-1,two,one,three); //最后再把n-1個(gè)從two移動(dòng)到three
    }
}


void move(char x,char y) // 定義move函數(shù)
{
    count++;
    if( !(count%5) )
        printf("\n");
    printf("%c移動(dòng)至%c ",x,y);
}