一般定義（來自網(wǎng)絡(luò)）：在調(diào)用一個函數(shù)的過程中又出現(xiàn)直接或間接地調(diào)用該函數(shù)本身归苍，就是函數(shù)的遞調(diào)用玛臂。
為求解規(guī)模為N的問題，設(shè)法將它分解成規(guī)模較小的問題堕担，然后從這些小問題的解方便地構(gòu)造出大問題的解介褥，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法座掘，分解成規(guī)模更小的問題，并從這些更小問題的解構(gòu)造出規(guī)模較大問題的解柔滔。特別地溢陪，當(dāng)規(guī)模N=1時，能直接得解廊遍。
遞歸算法的執(zhí)行過程分遞推和回歸兩個階段嬉愧。
在遞推階段，把較復(fù)雜的問題（規(guī)模為n）的求解推到比原問題簡單一些的問題（規(guī)模小于n）的求解喉前。
在回歸階段没酣，當(dāng)獲得最簡單情況的解后，逐級返回卵迂，依次得到稍復(fù)雜問題的解裕便。
在編寫遞歸函數(shù)時要注意，函數(shù)中的局部變量和參數(shù)知識局限于當(dāng)前調(diào)用層见咒，當(dāng)遞推進入“簡單問題”層時偿衰，原來層次上的參數(shù)和局部變量便被隱蔽起來。在一系列“簡單問題”層，它們各有自己的參數(shù)和局部變量下翎。由于遞歸引起一系列的函數(shù)調(diào)用缤言，并且可能會有一系列的重復(fù)計算，遞歸算法的執(zhí)行效率相對較低视事。
當(dāng)某個遞歸算法能較方便地轉(zhuǎn)換成遞推算法時胆萧，通常按遞推算法編寫程序。
總結(jié)一下：
1：遞歸算法的思想
遞歸算法是把問題轉(zhuǎn)化為規(guī)睦縮小了的同類問題的子問題跌穗。
然后遞歸調(diào)用函數(shù)（或過程）來表示問題的解。
在C語言中的運行堆棧為他的存在提供了很好的支持虏辫，過程一般是通過函數(shù)或子過程來實現(xiàn)蚌吸。
遞歸算法：在函數(shù)或子過程的內(nèi)部，直接或者間接地調(diào)用自己的算法砌庄。
2：遞歸算法的特點：
遞歸算法是一種直接或者間接地調(diào)用自身算法的過程羹唠。
在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的娄昆，它往往使算法的描述簡潔而且易于理解肉迫。
遞歸算法解決問題的特點：
(1) 遞歸就是在過程或函數(shù)里調(diào)用自身。
(2) 在使用遞歸策略時稿黄，必須有一個明確的遞歸結(jié)束條件，稱為遞歸出口跌造。
(3) 遞歸算法解題通常顯得很簡潔杆怕，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設(shè)計程序壳贪。
(4) 在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點陵珍、局部量等開辟了棧來存儲。遞歸次數(shù)過多容易造成棧溢出等违施。所以一般不提倡用遞歸算法設(shè)計程序互纯。
3：遞歸算法的要求
遞歸算法所體現(xiàn)的“重復(fù)”一般有三個要求：
一是每次調(diào)用在規(guī)模上都有所縮小(通常是減半)；
二是相鄰兩次重復(fù)之間有緊密的聯(lián)系磕蒲，前一次要為后一次做準(zhǔn)備(通常前一次的輸出就作為后一次的輸入)留潦；
三是在問題的規(guī)模極小時必須用直接給出解答而不再進行遞歸調(diào)用，因而每次遞歸調(diào)用都是有條件的(以規(guī)模未達到直接解答的大小為條件)辣往，無條件遞歸調(diào)用將會成為死循環(huán)而不能正常結(jié)束兔院。
我們看看幾個經(jīng)典遞歸問題
使用遞歸來解決斐波那契數(shù)列的第n個數(shù)是多少？（初始默認前兩個值是 1,2）斐波那契數(shù)列簡單來說就是下一個數(shù)是前兩個數(shù)的總和站削。不知道這個的話請自行g(shù)oogle腦補一下坊萝。利用遞歸思想，可以寫成如下代碼
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 的時候，就直接返回 index的值十偶；
當(dāng)index不為 1 或者 2 的時候菩鲜，就返回is_recursive_fib(index - 1) + is_recursive_fib(index - 2 )；
二話不說惦积，先上個小圖分析分析(畢竟沒有繪畫功底接校，見諒)
假設(shè)求第五個數(shù)，它的值是多少荣刑。
分析過程如下：
第一步馅笙，調(diào)用函數(shù) 傳遞參數(shù)是 5； 見 ①
第二步厉亏，拆解為 f(4) + f(3)董习； 見 ②
第三步，將左邊的f(4) 拆解為 f(3) + f(2)爱只；見 ③
第四步皿淋，將第三步分解出來f(3),再次拆分為 f(2) + f(1)； 見 ④
這個時候根據(jù)返回條件 index 是 1 或者 2恬试，就開始返回回去窝趣；
第五步，將f(2) + f(1) = 3的值返回回去训柴； 見⑤
這個時候f(3)得到返回的值 3哑舒， 然后和f(2) 相加計算得到值 是 5
第六步，將f(3) + f(2)的值為 5幻馁， 返回給 f(4);見 ⑥
這個時候 f(4)得到值 就是 5
第七步洗鸵，拆解右邊的 f(3)為 f(2) + f(1); 見 ⑦
這個時候 index為 1 和 2，滿足返回條件
第八步仗嗦，將 f(2) + f(1)的值 為 3 返回給 f（3）膘滨；見 ⑧
第九步，將左邊 f(4) 的值 5 和 右邊 f(3)的值 3 相加稀拐， 然后返回給 f（5）火邓；見⑨
最后，我們就得到f(5)的結(jié)果是 8.
前面已經(jīng)提到使用遞歸德撬，解決問題思路上會很簡單铲咨，但是效率卻非常低。
我們來改寫一下如果上面例子不用遞歸方法來實現(xiàn)蜓洪，改用 for循環(huán)迭代計算看看效果如何鸣驱。
先上代碼
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];
}
這個算法可以簡單看出 如果是 1 或者 2 就直接返回了結(jié)果。
如果大于2的話蝠咆， 怎定義一個數(shù)組踊东， 在for 循環(huán)那里北滥，每一次計算下一個值，下標(biāo)從3開始闸翅。
但是比較一下兩個的效率如何：
同一臺電腦設(shè)備前提下再芋， 我們設(shè)置求第45個值是多少
相比之下，用遞歸方法的 比 不是用遞歸方法的效率居然差 5倍之多坚冀！ 本文章例子在CodeBlocks 13.12版本測試通過**recursion.c
給一道課外習(xí)題
漢諾（Hanoi）塔問題：古代有一個梵塔济赎，塔內(nèi)有三個座A、B记某、C司训，A座上有64個盤子，盤子大小不等液南，大的在下壳猜，小的在上（如圖）。有一個和尚想把這64個盤子從A座移到B座滑凉，但每次只能允許移動一個盤子统扳，并且在移動過程中，3個座上的盤子始終保持大盤在下畅姊，小盤在上咒钟。在移動過程中可以利用B座，要求打印移動的步驟若未。如果只有一個盤子朱嘴，則不需要利用B座，直接將盤子從A移動到C粗合。
參考答案
/**
*
Tutorial 漢諾（Hanoi）塔問題
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); // 對move函數(shù)的聲明
void hanoi(int n,char one,char two,char three) ;// 對hanoi函數(shù)的聲明
int count = -1;
int main()
{
//hanoi函數(shù)
int m;
printf("請輸入一共有多少個板子需要移動:");
scanf("%d",&m);
printf("以下是%d個板子的移動方案:\n",m);
hanoi(m,'A','B','C');
return 0;
}
// 定義hanoi函數(shù)
// 將n個盤從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個從one移動到two
move(one,three); //然后把最后一個n從one移動到three
hanoi(n-1,two,one,three); //最后再把n-1個從two移動到three
}
}
void move(char x,char y) // 定義move函數(shù)
{
count++;
if( !(count%5) )
printf("\n");
printf("%c移動至%c ",x,y);
}
