資料結構學習筆記06-遞歸

遞歸

• 1.遞歸
• • 1.1 遞歸需要滿足的條件
  • 1.2 循環和遞歸的關系
• 2. 遞歸例題
• • 2.1 漢諾塔
  • 2.1 斐波那契數列
• 3. 遞歸的應用

1.遞歸

定義: 遞歸就是自己調用自己.

舉例: 求階乘,代碼如下:

int factorial(int n)
{
	if(n == 1)
		return 1;
	return n* factorial(n-1);
}
           

由以上的代碼可知:

• 遞歸就是函數自己調用自己；
• 遞歸需要有一個出口，不然會陷入死遞歸，上面的代碼中當n==1時即是出口；
• n的階乘可以看作是n乘以（n-1）的階乘，是以可以用遞歸。

類似于階乘，我們可以求一下累加，代碼如下：

int sum(int n)
{
	if(n == 1)
		return 1;
	return n+ sum(n-1);
}
           

1.1 遞歸需要滿足的條件

• 遞歸必須有一個明确的終止條件；
• 遞歸函數所處理的資料規模必須在遞減；
• 所有遞歸都可以用循環來實作。

1.2 循環和遞歸的關系

遞歸： 易于了解，速度慢，需要的存儲空間大；

循環： 不易了解。速度快，需要的存儲空間小。

2. 遞歸例題

2.1 漢諾塔

問題：

　　漢諾塔是一個古老的數學問題：

　　有三根杆子A，B，C。A杆上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則将所有圓盤移至C杆：

　　每次隻能移動一個圓盤；

　　大盤不能疊在小盤上面。

　　提示：可将圓盤臨時置于B杆，也可将從A杆移出的圓盤重新移回A杆，但都必須遵循上述兩條規則。請問要怎麼移動？

　　

思路：

• 第一步：先把A上的前n-1個盤子從A借助C移到B；
• 第二步：将A的第n個盤子移動到C；
• 第三步： 再将B上的n-1個盤子移動到C。

代碼：

#include<stdio.h>

//t1是盤子所在的塔, t2是中間塔,t3是目标塔 ,h是塔高 
void HNT(char t1,char t2,char t3,int h)
{
	//當盤子隻有一個的時候直接移動到目标塔上即可 
	if(h == 1)
	{
		printf("從%c挪到%c\n",t1,t3); 
	 	return; 
	} 
	//第一步 
	HNT(t1,t3,t2,h-1);
	//第二步 
	printf("從%c挪到%c\n",t1,t3);
	//第三步 
	HNT(t2,t1,t3,h-1);
	return; 
}


int main(void)
{
	HNT('A','B','C',3); 
	return 0;
} 
           

2.1 斐波那契數列

問題：

斐波那契數列預設第一項和第二項都是1，後面每一項都是前兩項之和，即為一個 1，1，2，3，5，8，…的數列，求斐波那契數列中的某一項。

代碼：

int fei(int n)
{
	if(n == 1 || n == 2)
	 	return 1;
	return fei(n-1) + fei(n-2); 
}
           

注：

對于斐波那契數列這種問題，當n的值變大時使用遞歸需要經過很多次的運算，需要耗費很多的時間，是以更加推薦使用動态規劃來解題，動态規劃是一種犧牲少量空間換取大量時間的方法，代碼如下：

int fei(int n)
{
	int a[n];
	a[0] = 1;
	a[1] = 1;
	for(int i = 2;i<n;i++)
		a[i] = a[i-1] + a[i-2];
	return a[n-1];
}

           

之後有機會會詳細解釋動态規劃，在這裡隻是多句嘴。

3. 遞歸的應用

• 樹和森林就是以遞歸的方式定義的；
• 樹和圖的很多算法都是以遞歸的方式實作的；
• 很多數學公式就是以遞歸的方式定義的。