遞歸法：
通過自身調(diào)用自身來達(dá)到問題解決的算法褂萧。一般押桃，我們用歸納法是證明遞歸算法正確性和進(jìn)行算法分析
原問題無法解決唱凯，用分治的的思想將其分解羡忘，若分解后的子問題仍無法解決就再次分解，直到分成的子問題規(guī)模足夠小可以直接解決磕昼，然后將子問題合并得到原問題的解卷雕。
遞歸思想就是用與自身問題相似但規(guī)模較小的問題來描述自己漫雕。遞歸算法的執(zhí)行過程劃分為遞推和回歸兩個階段。在遞推階段峰鄙，把規(guī)模為n的問題的求解推到比原問題的規(guī)模較小的問題求解浸间，且必須要有終止遞歸的條件。在回歸階段吟榴，當(dāng)獲得最簡單情況的解后魁蒜，逐級返回，依次得到規(guī)模較大問題的解吩翻。就像打開一扇門里面還有一扇門兜看，重復(fù)直到門里面沒有門，然后再從一扇有一扇門中走出來狭瞎。
（1）求解規(guī)模為n的問題可以轉(zhuǎn)化為一個或多個結(jié)構(gòu)相同、規(guī)模較小的問題球涛，然后從這些小問題的解能方便地構(gòu)造出大問題的解劣针。相鄰兩次重復(fù)之間有緊密的聯(lián)系，前一次要為后一次做準(zhǔn)備(通常前一次的輸出就作為后一次的輸入)亿扁。
（2）遞歸調(diào)用的次數(shù)必須是有限的捺典，每次遞歸調(diào)用后必須越來越接近某種限制條件。
（3）必須有結(jié)束遞歸的條件（邊界條件）來終止遞歸从祝。當(dāng)遞歸函數(shù)符合這個限制條件時襟己，它便不在調(diào)用自身，即當(dāng)規(guī)模n=1時牍陌，能直接得解。
舉個栗子：（全排列毒涧、組合、深度優(yōu)先搜索等仿吞。在數(shù)據(jù)結(jié)構(gòu)中，樹峡迷、二叉樹和列表常采用遞歸方式來定義你虹。）
一堆產(chǎn)品中有一個次品存在，若這個次品與合格品的區(qū)別只是重量的不同售葡，要找出這個次品看杭。用遞歸法解時：先將這一堆產(chǎn)品分成個數(shù)一樣的兩堆忠藤。進(jìn)行稱重后必然有一端重一端輕挟伙，此時還無法判斷次品所在；然后繼續(xù)對每部分的n/2個產(chǎn)品再進(jìn)行分組和稱重模孩，如果平衡則這部分的n/2個產(chǎn)品都為正品尖阔，即次品在另外那部分中，否則次品就在這n/2個產(chǎn)品中榨咐。這樣尋找次品的范圍就減少了一半介却。依照這種方法不斷縮小次品的范圍，直到最后一對一找出次品块茁。
再來一個栗子
求階乘問題：
詳細(xì)說說遞推和回歸：
遞推（時間復(fù)雜度計算）：
遞推方程-->遞歸方程
計算遞推式的方法：
1、迭代法
2李滴、替換方法：猜遞推式的解的范圍（漸近復(fù)雜度的上下界），然后用數(shù)學(xué)歸納法證明是否存在滿足條件的解所坯。
3挂捅、公式法：
回歸（應(yīng)用舉例）：
-
漢諾塔問題
把圓盤按大小順序重新擺放在另一根柱子上：在三根柱子之間一次只能移動個圓盤。移動的時候始終只能小圓盤壓著大圓盤酱讶。盤子只能在三個柱子上存放
#include<iostream>
using namespace std;
void move(int n,char x,char y)
{
cout<<"把"<<n<<"號從"<<x<<"挪動到"<<y<<endl;
}
void Hannoi(int n,char A,char B,char C) //將n個盤子從A柱借助B柱移動C柱
{
if(n==1) //遞歸終止條件
move(1,A,C);
else
{
Hannoi(n-1,A,C,B); //遞歸調(diào)用
move(n,A,C);
Hannoi(n-1,B,A,C); //遞歸調(diào)用
}
}
int main()
{
int n;
cout<<”請輸入盤子的個數(shù)：”<<endl;
cin>>n;
Hannoi(n,'A','B','C');
return 0;
}
經(jīng)過分析得：
(1)將n個盤子上面的n-1個盤子借助C柱從A柱移到 B柱上泻肯，需要count（n-1）次；
(2)將A柱上第n個盤子移到C柱毒租，花費1次惕医；
(3)將B柱上的n-1個盤子借助A柱移到C柱抬伺，需要count（n-1）次峡钓；
移動次數(shù)也可用遞歸法計算：
#include <iostream>
using namespace std;
int main()
{
int num，count=0;
cout<<"請輸入需要移動的盤子數(shù)目："<<endl;
cin>>num;
int val(int); //函數(shù)聲明
if(num==0){
cout<<"輸入的數(shù)字必須大于0!"<<endl;
return -1;
}
else
cout<<"需要"<<val(num)<<"次"<<endl;
return 0;
}
int val(int n){
int c;
if(n==1) c=1;
else c=2*val(n-1)+1;
return c;
}
-
斐波那契數(shù)列問題
求第n個數(shù)值
#include<iostream.h>
int fib(int n)
{
int f=0;
if(n==1) return 0;
if(n==2) return 1;
f=fib(n-1)+fib(n-2);
return f;
}
int main()
{
int n,i,m=0;
cin>>n;
m=fib(n);
cout<<"第"<<n<<"項是"<<m<<endl;
m=0;
for(i=1;i<=n;i++)
m=fib(i)+m;
cout<<"前"<<n<<"項和是"<<m<<endl;
return 0;
}
-
八皇后問題
在8×8格的國際象棋棋盤上放置八個皇后，使得任意兩個皇后不能互相攻擊毛俏，即任何行煌寇、列或?qū)蔷€上不得有兩個或兩個以上的皇后阀溶。這樣的一個格局稱為問題的一個解银锻。原文鏈接：[http://www.reibang.com/p/65c8c60b83b8]
#include<iostream>
using namespace std;
const int Normalize=9; //定義常量鼎姐，用來統(tǒng)一數(shù)組下標(biāo)
int Num=0; //整型變量炕桨，記錄方案數(shù)
int Queen[9]; //記錄8個皇后所占用的列號
bool C[9]; //C[1]~C[8]布爾型變量献宫，判斷當(dāng)前列是否可行
bool L[17]; //L[2]~L[16]布爾型變量姊途，判斷(i-j)對角線是否可行
bool R[17]; //R[2]~R[16]布爾型變量吭净，判斷(i+j)對角線是否可行
void check(int i) //被調(diào)用函數(shù)
{
int j; //循環(huán)變量，表示列號
int k; //臨時變量
for(j=1;j<=8;j++)
{
if((C[j]==true) &&(R[i+j]==true)&&(L[i-j+Normalize]==true))
//表示第i行第j列可行
{
Queen[i]=j; //占用位置(i,j)
C[j]=false; //修改可行標(biāo)志原在，包括所在列和兩個對角線
L[i-j+Normalize]=false;
R[i+j]=false;
if(i<8) //判斷是否放完8個皇后
{
check(i+1); //未放完8個皇后則繼續(xù)放下一個
}
else //已經(jīng)放完8個皇后
{
Num++; //方案數(shù)加1
cout<<"方案"<<Num<<":"<<"\t";//輸出方案號
for(k=1;k<=8;k++)
cout<<k<<"行"<<Queen[k]<<"列"<<"\t";//輸出具體方案
cout<<endl; //換行
}
C[j]=true; //修改可行標(biāo)志，回溯
L[i-j+Normalize]=true;
R[i+j]=true;
} //循環(huán)結(jié)束
}
} //check函數(shù)結(jié)束
int main() //主函數(shù)
{
int i; //循環(huán)變量
Num=0; //方案數(shù)清零
for(i=1;i<9;i++) //置所有列可行
C[i]=true;
for(i=0;i<17;i++) //置所有對角線可行
L[i]=R[i]=true;
check(1); //遞歸放置8個皇后浮庐，從第一行開始放
return 0;
}
優(yōu)缺點
優(yōu)點：
處理重復(fù)性計算時审残，遞歸往往使函數(shù)的定義和算法的描述簡單明了搅轿、易于理解璧坟、容易編程和驗證雀鹃。
缺點
遞歸的運算方法黎茎，決定了它的效率較低工三，一是數(shù)據(jù)要不斷進(jìn)出棧俭正，另一就是存在大量的重復(fù)計算串远，這樣使得應(yīng)用遞歸時澡罚，輸入的n值稍大留搔，程序的求解就變得比較困難隔显，故在有些情況下括眠，遞歸可以轉(zhuǎn)化為效率較高的非遞歸掷豺。
