cuicuiv小白學(xué)算法—遞歸

遞歸：是指在函數(shù)的定義中又調(diào)用函數(shù)自身的方法。

使用遞歸求解的問(wèn)題需要滿足一下三個(gè)條件：

需要解決的問(wèn)題可以轉(zhuǎn)化為一個(gè)或多個(gè)子問(wèn)題來(lái)求解，而這些子問(wèn)題的求解方法與原問(wèn)題完全相同，只是在數(shù)量規(guī)模上不同。

遞歸調(diào)用的次數(shù)必須是有限的。

必須有結(jié)束遞歸的條件來(lái)終止遞歸

提取遞歸模型的步驟

對(duì)原問(wèn)題f(s_n)進(jìn)行分析，抽象出合理的“小問(wèn)題”f(s_n-1)

假設(shè)f(s_n-1)是可解的，在此基礎(chǔ)上確定f(s_n)的解，即給出f(s_n)和f(s_n-1)之間的關(guān)系

確定一個(gè)特定情況(如f(1)和f(0))的解，由此作為遞歸的出口

基于遞歸數(shù)據(jù)結(jié)構(gòu)的遞歸算法設(shè)計(jì)

例—二叉樹(shù)的遞歸算法設(shè)計(jì)

假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)遞歸算法釋放二叉樹(shù)bt中的所有結(jié)點(diǎn)。

---

設(shè)f(bt)的功能是釋放二叉樹(shù)bt的所有結(jié)點(diǎn)，則f(bt->lchild)的功能是釋放二叉樹(shù)bt的左子樹(shù)的所有結(jié)點(diǎn)，f(bt->rchild)的功能是釋放二叉樹(shù)bt的右子樹(shù)的所有結(jié)點(diǎn)。即f(bt)是“大問(wèn)題”，f(bt->lchild)和f(bt->rchild)是兩個(gè)“小問(wèn)題”
對(duì)應(yīng)的遞歸模型如下：
f(bt)=不做任何事情 ********************************** 當(dāng)bt=NULL時(shí)
f(bt)=f(bt->lchild);f(bt->rchild);釋放bt所指的結(jié)點(diǎn) ***其他情況
*
對(duì)應(yīng)的遞歸算法：
void DestroyBtree(BTNode *&bt)
{ if(bt!=NULL)
{
DestroyBtree(bt->lchild);
DestroyBtree(bt->rchild);
ftee(bt);
}
}

基于歸納思想的遞歸算法設(shè)計(jì)

從本質(zhì)上來(lái)講，給出一個(gè)帶有參數(shù)n的問(wèn)題，采用基于歸納思想設(shè)計(jì)遞歸算法是基于這樣一個(gè)事實(shí)。
如果知道求解帶有參數(shù)k(<n)的同樣問(wèn)題，那么整個(gè)任務(wù)就轉(zhuǎn)化成如何把解法擴(kuò)展到帶有參數(shù)k的情況。實(shí)際上就是以f(n)為“大問(wèn)題”，以f(n-1)或者f(n/2)等為“小問(wèn)題”，歸納出大小問(wèn)題之間的遞推關(guān)系。

基于歸納思想的遞歸算法設(shè)計(jì)通常不像基于遞歸數(shù)據(jù)結(jié)構(gòu)的遞歸算法設(shè)計(jì)那樣直觀，需要通過(guò)對(duì)求解問(wèn)題的深入分析提煉出求解過(guò)程中的相似性而不是數(shù)據(jù)結(jié)構(gòu)的相似性，這就增加了算法設(shè)計(jì)的難度。

簡(jiǎn)單選擇排序和冒泡排序
【問(wèn)題描述】 對(duì)于給定的含有n個(gè)元素的數(shù)組a，分別采用簡(jiǎn)單選擇排序和冒泡排序方法按元素值遞增排序

---

簡(jiǎn)單選擇排序和冒泡排序方法都是按a[0···n-1]分為有序區(qū)a[0····i-1]和無(wú)序區(qū)兩個(gè)部分，有序區(qū)中的所有元素都不大于無(wú)序區(qū)中的元素，初始時(shí)有序區(qū)為空(即i=0)。經(jīng)過(guò)n-1趟排序(i=1~n-2)，每趟排序采用不同方式將無(wú)序區(qū)中的最小元素移動(dòng)到無(wú)序區(qū)的開(kāi)頭。

---

1.簡(jiǎn)單選擇排序

簡(jiǎn)單選擇排序采用簡(jiǎn)單比較方式在無(wú)序區(qū)中選擇最小元素并放到開(kāi)頭處。
設(shè)f(a,n,i)用于在無(wú)序區(qū)a[i···n-1]（共n-i個(gè)元素）中選擇最小元素并放到a[i]處，是“大問(wèn)題”，則f(a,n,i+1)用于在無(wú)序區(qū)a[i+1····n-1]中選擇最小元素放到a[i+1]處，是“小問(wèn)題”。當(dāng)i=n-1時(shí)所有元素有序，算法結(jié)束。

---

對(duì)應(yīng)遞歸模型：
f(a,n,i) 不做任何事情，算法結(jié)束****************************當(dāng)i=n-1時(shí)
f(a,n,i) 通過(guò)簡(jiǎn)單選擇比較挑選a[i···n-1]中最小的元素；***否則
a[k]放到a[i]出；f(a,n,i+1);

代碼如下：

#include<stdio.h> void swap(int &x,int &y) //交換x和y的值 {int tmp=x;x=y;y=tmp; }void disp(int a[],int n) //輸出a中的所有元素 {for(int i=0;i<n;i++)printf("%d",a[i]);printf("\n"); }void SelectSort(int a[],int n,int i) //遞歸的簡(jiǎn)單選擇 {int j,k;if(i==n-1) return; //滿足遞歸出口else {k=i;//k記錄a [i ```n-1]中最小元素的下標(biāo)for(j=i+1;j<n;j++)//在a[i```n-1]中找最小元素a[k]{if(a[j]<a[k])k=j;if(k!=i)//若最小元素不是a[i]swap(a[i],a[k]);//a[i]和a[k]交換SelectSort(a,n,i+1);} } } void main() {int n=10;int a[]={2,5,1,7,10,6,9,4,3,8};printf("排序前：");disp(a,n);SelectSort(a,n,0);printf("排序后：");disp(a,n); }

簡(jiǎn)單選擇排序通過(guò)兩兩對(duì)比一一得出最小元素，通過(guò)遞歸實(shí)現(xiàn)全部排列，最后通過(guò)遞歸出口結(jié)束。

---

2.冒泡排序

冒泡排序采用交換方式將無(wú)序區(qū)中的最小元素放到開(kāi)頭處。

---

設(shè)f(a,n,i)用于將無(wú)序區(qū) a[i···n-1] 中的最小元素交換到a[i]處，是”大問(wèn)題“，則f(a,n,i+1)用于將無(wú)序區(qū)a[i+1···n-1]中的最小元素交換到a[i+1]處，是”小問(wèn)題“。當(dāng)i=n-1時(shí)所有元素有序，算法結(jié)束。

---

對(duì)應(yīng)遞歸模型：
f(a,n,i) 不做任何事情，算法結(jié)束************************當(dāng)i=n-1時(shí)
f(a,n,i) 對(duì)a[i ···n-1]中的元素序列從a[n-1]開(kāi)始進(jìn)行相鄰比較***否則
若相鄰兩元素反序則將兩者交換；
若沒(méi)有交換則返回，否則執(zhí)行f(a,n,i+1)

代碼如下：

#include<stdio.h> void swap(int &x,int &y) //交換x和y的值 {int tmp=x;x=y;y=tmp; }void disp(int a[],int n) //輸出a中的所有元素 {for(int i=0;i<n;i++)printf("%d",a[i]);printf("\n"); }void BubbleSort(int a[],int n,int i) //遞歸的冒泡排序 {int j;bool exchange;if(i==n-1) return; //滿足遞歸出口條件else{exchange=false;for(j=n-1;j>i;j--)if(a[j]<a[j-1]) // 當(dāng)相鄰元素方序時(shí){swap(a[j],a[j-1]);exchange=true;} if(exchange==false) //未發(fā)生交換時(shí)直接返回return;elseBubbleSort(a,n,i+1);} } void main() {int n=10;int a[]={2,5,1,7,10,6,9,4,3,8};printf("排序前：");disp(a,n);SelectSort(a,n,0);printf("排序后：");disp(a,n); }

**

總結(jié)：

1. 面對(duì)問(wèn)題求解選擇方法時(shí)，先判斷題目對(duì)象的條件，以其數(shù)據(jù)結(jié)構(gòu)以及數(shù)學(xué)模型為參考。
2. 用遞歸求解題目主要分為兩大類：
（1）基于遞歸數(shù)據(jù)結(jié)構(gòu)的遞歸算法設(shè)計(jì) （2）基于歸納思想的遞歸算法設(shè)計(jì)
3.使用遞歸時(shí)，對(duì)“大問(wèn)題”和“小問(wèn)題”的判斷以及劃分以及遞歸出口條件極為重要。

總結(jié)

以上是生活随笔為你收集整理的算法设计学习---递归的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。