什么是遞歸？

要說(shuō)到遞歸如果不說(shuō)棧的話(huà)，我覺(jué)得有點(diǎn)不合適，遞歸特點(diǎn)就是不斷的調(diào)用同一個(gè)函數(shù)，如果這個(gè)函數(shù)沒(méi)有一個(gè)遞歸界限，那么就是死循環(huán)了，所以討論遞歸，就必須要討論遞歸的界限，就是限定這個(gè)遞歸調(diào)用多少次。

我們看一個(gè)例子

#include "stdio.h"

int digui(unsigned long count )
{
	if(count > 0){
		count --;
		printf("%d \\n",count);
		digui(count);
	}
	return 1;
}

int main()
{
	digui(10);
	return (100);
}

這個(gè)遞歸函數(shù)的限定判讀是

if(count > 0){

所以他的調(diào)用順序可以用這個(gè)圖示來(lái)說(shuō)明

這個(gè)過(guò)程叫做遞去，也就是壓棧的過(guò)程，既然有壓棧的過(guò)程，那么就有出棧的過(guò)程，出棧的過(guò)程就是

if(count > 0){

判斷不成功后，就會(huì)出棧了。如下圖所示

一共能執(zhí)行多少次遞歸？

我們上面說(shuō)到了，既然遞歸使用了棧，那么系統(tǒng)的棧的大小肯定是有極限的，不可能系統(tǒng)給你分配無(wú)極限的棧的大小，我看一些文章說(shuō)棧大小是64K。

還是上面那個(gè)例子，我把傳入數(shù)據(jù)設(shè)置為很大執(zhí)行看看。

#include "stdio.h"

int tigui(unsigned long count )
{
	if(count > 0){
		count --;
		printf("%d \\n",count);
		tigui(count);
	}
	return 1;
}

int main()
{
	tigui(900000);
	return (100);
}

執(zhí)行結(jié)果

所以說(shuō)遞歸次數(shù)肯定是有限定的了。

遞歸求階乘

使用遞歸求階乘是很經(jīng)典的方法，我們看一下代碼。

#include< stdio.h >
int fact(unsigned long n); //聲明階乘fact函數(shù)
int main(){
	 unsigned long x;
	 scanf("%d",&x);
	 x = fact(x);//調(diào)用函數(shù)返回int值
	 printf("%ld\\n",x);
	 return (0);
}
int fact(unsigned long n){//定義階乘函數(shù)
	if(n==1) return 1;//輸入的參數(shù)是1，直接返回1
	else return n*fact(n-1);//遞歸算法
}

執(zhí)行結(jié)果

單看代碼我覺(jué)得還是有點(diǎn)拗口我們看個(gè)圖片來(lái)看他的調(diào)用，假設(shè)我們要求的是 5 的階乘

遞歸和漢諾塔

漢諾塔： 漢諾塔（又稱(chēng)河內(nèi)塔）問(wèn)題是源于印度一個(gè)古老傳說(shuō)的益智玩具。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤(pán)。大梵天命令婆羅門(mén)把圓盤(pán)從下面開(kāi)始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤(pán)上不能放大圓盤(pán)，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤(pán)。

如果是這樣的漢諾塔，我覺(jué)得應(yīng)該每個(gè)人都覺(jué)得很簡(jiǎn)單吧，只需要三步就可以完成移動(dòng)。

1、把小圓盤(pán)放到第三根柱子上
2、把中圓盤(pán)放到第二根柱子上
3、把小圓盤(pán)放到第二根柱子上
4、把大圓盤(pán)放到第三根柱子上
5、把小圓盤(pán)放到第一根柱子上
6、把中圓盤(pán)放到第三根柱子上
7、把小圓盤(pán)放到第三根柱子上

如圖所示

剖析我們上面是細(xì)分的方法，移動(dòng)的核心思想分為三步。

1、把第一個(gè)柱子上的n-1圓盤(pán)移動(dòng)到第二個(gè)柱子上。
2、把第一個(gè)柱子的第n個(gè)圓盤(pán)移動(dòng)到第三個(gè)柱子上。
3、把第二個(gè)柱子的n-1個(gè)圓盤(pán)移動(dòng)到第三個(gè)柱子。

所以遞歸就出現(xiàn)了

1、把第一個(gè)柱子上的n-1圓盤(pán)移動(dòng)到第二個(gè)柱子上「 遞歸實(shí)現(xiàn) 」。
2、把第一個(gè)柱子的第n個(gè)圓盤(pán)移動(dòng)到第三個(gè)柱子上。
3、把第二個(gè)柱子的n-1個(gè)圓盤(pán)移動(dòng)到第三個(gè)柱子「 遞歸實(shí)現(xiàn) 」。

C語(yǔ)言代碼實(shí)現(xiàn)

#include < stdio.h >
#include < windows.h >
void Hanoi(int n, char a,char b,char c);
void Move(int n, char a, char b);
int count;
int main()
{
    int n=8;
    printf("漢諾塔的層數(shù):\\n");
    scanf(" %d",&n);
    Hanoi(n, 'A', 'B', 'C');
    printf("Exiting main...\\n");
    return 0;
}
void Hanoi(int n, char a, char b, char c)
{
    if (n == 1)
    {
        Move(n, a, c);
    }
    else
    {
        Hanoi(n - 1, a, c, b);/*把 n-1 從 a 柱子放到 b 柱子上面*/
        Move(n, a, c);        /*把 n 從 a 移動(dòng)到 c 上*/
        Hanoi(n - 1, b, a, c);/*把n - 1 通過(guò) a 的輔助作用 從 b 移動(dòng)到 c 上*/
    }
}
void Move(int n, char a, char b)
{
    count++;
    printf("第%d次移動(dòng) Move %d: 從 %c 位置 移動(dòng)到 %c !\\n",count,n,a,b);
}

輸出如圖所示

加強(qiáng)版修改

加強(qiáng)了下軟件寫(xiě)法，好好看代碼，寫(xiě)的有點(diǎn)太快，沒(méi)細(xì)想，后面再完善。

#include < stdio.h >

/*柔性數(shù)組*/
typedef struct _soft_array{
	int len;
	int array[];
}soft_array;

/*漢諾塔結(jié)構(gòu)體*/
typedef struct _hannuo{
	soft_array *p_data;
	char name;
}hannuo;

hannuo * han_a = NULL;
hannuo * han_b = NULL;
hannuo * han_c = NULL;

void hannoiii(int n,hannuo * a,hannuo * b,hannuo * c);
void moveiii (int n,hannuo * a,hannuo * c);

int total;

void printf_han_data(hannuo * han)
{
	int i = 0;
	printf("%c: ",han- >name);
	/*輸出漢諾塔的數(shù)據(jù)*/
	for(i = 0;i< han- >p_data- >len;i++)
	{
		printf("%d-",han- >p_data- >array[i]);
	}
	printf("\\n");	
}


int main()
{
	int i = 0;
	int n = 0;

	scanf(" %d",&n);
	total = n;
	/*定義三個(gè)漢諾塔節(jié)點(diǎn)*/
	han_a = (hannuo *)malloc(sizeof(hannuo));
	han_a- >name = 'A';
	han_a- >p_data = (soft_array*)malloc(sizeof(soft_array)+sizeof(int)*n);
	han_a- >p_data- >len = n;
	
	/*數(shù)據(jù)原來(lái)在第一根柱子上*/
	for(i = 0;i< n;i++)
	{
		han_a- >p_data- >array[i] = i+1;
	}
	printf_han_data(han_a);
	
	/*初始化第二根柱子*/
	han_b = (hannuo *)malloc(sizeof(hannuo));
	han_b- >name = 'B';
	han_b- >p_data = (soft_array*)malloc(sizeof(soft_array)+sizeof(int)*n);
	memset(han_b- >p_data,0,sizeof(soft_array)+sizeof(int)*n);
	han_b- >p_data- >len = n;
	printf_han_data(han_b);
	/*初始化第三根柱子*/
	han_c = (hannuo *)malloc(sizeof(hannuo));
	han_c- >name = 'C';
	han_c- >p_data = (soft_array*)malloc(sizeof(soft_array)+sizeof(int)*n);
	memset(han_c- >p_data,0,sizeof(soft_array)+sizeof(int)*n);
	han_c- >p_data- >len = n;
	printf_han_data(han_c);
	printf("------------------------\\n");
	hannoiii(n,han_a,han_b,han_c);
	

	printf("\\n");
    return 0;
}

void hannoiii(int n,hannuo * a,hannuo * b,hannuo * c)
{
	if(n == 1)
	{
		a- >p_data- >array[0] = 0;
		c- >p_data- >array[0] = 1;
		printf_han_data(han_a);
		printf_han_data(han_b);
		printf_han_data(han_c);
		printf("------------------------\\n");
	}
	else
	{
		hannoiii(n - 1, a, c, b);/*把 n-1 從 a 柱子放到 b 柱子上面*/
        moveiii(n, a, c);        /*把 n 從 a 移動(dòng)到 c 上*/
		printf_han_data(han_a);
		printf_han_data(han_b);
		printf_han_data(han_c);
		printf("------------------------\\n");
        hannoiii(n - 1, b, a, c);/*把n - 1 通過(guò) a 的輔助作用 從 b 移動(dòng)到 c 上*/
	}
}

void moveiii (int n,hannuo * a,hannuo * c)
{
    int i = 0;
    int tmp = a- >p_data- >array[n-1];
	a- >p_data- >array[n-1] = 0;
	#if 1
	c- >p_data- >array[n-1] = tmp;
	#else
	for(i = 0;i < total;i++)
	{
	    if(c- >p_data- >array[i] == 0){
	        c- >p_data- >array[i] = tmp;
	        break;
	    }
	}
	#endif
}

聲明：本文內(nèi)容及配圖由入駐作者撰寫(xiě)或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀(guān)點(diǎn)僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問(wèn)題，請(qǐng)聯(lián)系本站處理。舉報(bào)投訴