遞歸（英語：Recursion）齿坷，又譯為遞回，在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，是指在函數(shù)的定義中使用函數(shù)自身的方法译暂。遞歸一詞還較常用于描述以自相似方法重復(fù)事物的過程
------------------維基百科
我記得大學(xué)計(jì)算機(jī)結(jié)構(gòu)與算法的一節(jié)課上，老師給我們講解了遞歸的整個(gè)調(diào)用過程撩炊，印象還挺深刻的外永，因?yàn)槔蠋熣f，拧咳，伯顶。遞歸，就是有遞有歸骆膝，有個(gè)問題，我們解決不了，但是我們可以不斷的將問題簡(jiǎn)化成相同問題的子問題鲫剿，直到子化成我們可以解決的問題枕面，返回一個(gè)解決方法，然后這個(gè)解決方法可以解決更大的問題并返回一個(gè)解決方法政钟，如此反復(fù)路克，大問題就解決了，其實(shí)遞歸是一種解決問題的手段养交，而這種思想就是分治思想精算，對(duì)工作中生活中解決問題非常有幫助。
遞歸一般都有一個(gè)遞歸函數(shù)碎连，這個(gè)函數(shù)直接調(diào)用自己或者通過一系列的調(diào)用語句間接的調(diào)用自己灰羽，
而函數(shù)里邊一般都會(huì)有兩部分，
- 遞歸結(jié)束條件的語句破花，邊界條件谦趣；
- 遞歸調(diào)用自己的語句，簡(jiǎn)化問題座每。
如果不理解遞歸前鹅，那這個(gè)模版也可以套用吧。不過分治的思想真的很重要峭梳，需要掌握舰绘。
接下來可以分析一些實(shí)際的問題來幫助我們更加理解蹂喻，先從hello world式的N的階乘開始
- 計(jì)算n!的階乘，原始的計(jì)算機(jī)自然一下子當(dāng)然難以計(jì)算捂寿，但是我們只要計(jì)算出(n-1)!了口四，n!就能通過(n-1)*n計(jì)算出來了呀。那結(jié)束條件是n=1的時(shí)候秦陋，我們讓1!=1蔓彩，這樣，當(dāng)n不斷遞減驳概，到1的時(shí)候赤嚼，我們就能得到結(jié)果了
//計(jì)算n!
//構(gòu)造一個(gè)遞歸函數(shù)，兩個(gè)部分：
//n=1 的時(shí)候顺又，返回1更卒，因?yàn)?的階乘就等于1；
//n!=1 的時(shí)候稚照，繼續(xù)調(diào)用自己蹂空，計(jì)算n-1的階乘，并返回n \* (n-1)!果录；
int recursion(int n) {
if (n == 1) {
return 1;
}
return recursion(n-1)*n;
}
- POJ 1664 把M個(gè)同樣的蘋果放在N個(gè)同樣的盤子里上枕，允許有的盤子空著不放，問共有多少種不同的分法雕憔？
這道題類似整數(shù)劃分問題姿骏，整數(shù)劃分使用了一個(gè)相加的個(gè)數(shù)來輔助遞歸，這種遞歸有兩種情況：
//n>m,有n-m個(gè)盤子是空的斤彼，這幾個(gè)盤子不影響結(jié)果, fun(m,n)=fun(m,m)
//n<m,
//1,至少一個(gè)盤空著：f(m,n)=f(m,n-1)
//2,所有盤都放了蘋果：f(m,n)=f(m-n,n)
//結(jié)果= 情況1+情況2..
int fun(int m, int n) {
if(m==0 || n == 1)
return 1;
if(n>m)
return fun(m,m);
else
return fun(m,n-1)+fun(m-n,n);
}
- Hanoi Tower 漢諾塔問題
這個(gè)問題應(yīng)該都很熟悉了,有三個(gè)桌子a,b,c, 從a移動(dòng)n個(gè)盤子到c,我們不知道怎么移,但是我們可以把移動(dòng)n-1個(gè)盤子當(dāng)作一個(gè)整體子問題分瘦，然后在這個(gè)基礎(chǔ)上做些移動(dòng)操作然后完成移動(dòng)n個(gè)盤子的操作。
// 問題hanoi(a,b,c,n)：
// 三個(gè)操作：
// 把n-1個(gè)盤子從a移動(dòng)到b; hanoi(a,c,b,n-1)
// 把第n個(gè)盤子從a移動(dòng)到c; move(a,c)
// 把n-1個(gè)盤子從b移動(dòng)到c; hanoi(b,a,c,n-1)
void hanoi(char a, int b, int c, int n) {
if(n == 1)
printf("\n%c->%c\n"a,c);
else {
hanoi(n-1,a,c,b);
printf("\n%c->%c\n"a,c);
hanoi(n-1,b,a,c);
}
}
- 斐波拉契數(shù)列求和
//典型的遞歸問題
int Fibonacci(int n){
if (n <= 1)
return n;
else
return Fibonacci(n-1) + Fibonacci(n-2);
}
- 輸入字符串琉苇，反轉(zhuǎn)輸出嘲玫，類似的還有判斷一段字符串回文等
//字符串反轉(zhuǎn)輸出，其實(shí)是利用了遞歸的從最里層返回的特性
void recursion() {
char t;
cin >> t;
if (t == '1') {
return;
}
if (t != '1') {
recursion();
printf("%c",t);
}
}
遞歸的簡(jiǎn)單分析：遞歸雖然易讀并扇，而且簡(jiǎn)單去团，但是他的運(yùn)行效率較低，時(shí)間穷蛹，空間復(fù)雜度都比非遞歸算法要高土陪。因?yàn)檫f歸調(diào)用實(shí)際上是函數(shù)自己在調(diào)用自己，而函數(shù)的調(diào)用開銷很大肴熏，系統(tǒng)要為每次函數(shù)調(diào)用分配存儲(chǔ)空間鬼雀，并將調(diào)用點(diǎn)壓棧予以記錄。而在函數(shù)調(diào)用結(jié)束后蛙吏，還要釋放空間源哩，彈椥恢復(fù)斷點(diǎn)。所以說励烦，函數(shù)調(diào)用不僅浪費(fèi)空間谓着，還浪費(fèi)時(shí)間。
比如說坛掠，求n的階乘赊锚，其實(shí)如果使用迭代法來計(jì)算的話，他們的時(shí)間復(fù)雜度都是O(n),但是由于遞歸會(huì)需要多次發(fā)生函數(shù)調(diào)用屉栓，所以遞歸算法來計(jì)算的效率還是會(huì)低一些的改抡。
