C語(yǔ)言深入探索遞歸的特點(diǎn)

更新時(shí)間：2022年06月07日 10:42:51 作者：沙漠下的胡楊

程序調(diào)???的編程技巧稱為遞歸 recursion）函數(shù)??調(diào)???就是遞歸，你也可以理解成是?種嵌套結(jié)構(gòu)，但遞歸分為倆部分，第?是“遞”，進(jìn)?嵌套結(jié)構(gòu)。第?是”歸“，最終會(huì)?步?步返回。第?次接觸遞歸都會(huì)很懵，慢慢理解這個(gè)過(guò)程就明?了

遞歸的認(rèn)識(shí)

基本認(rèn)識(shí)：

1.首先遞歸的本質(zhì)還是函數(shù)調(diào)用，也要形成和釋放棧幀。

2.函數(shù)的調(diào)用是有成本的，這個(gè)成本在時(shí)間和空間上表現(xiàn)為函數(shù)棧幀的形成和銷毀。

3.遞歸就是不斷形成棧幀和銷毀的過(guò)程。

理論認(rèn)識(shí)：

1.內(nèi)存和cpu中的資源有限，也就決定啦，合理的遞歸是絕對(duì)不可以無(wú)限遞歸下去的。

2.遞歸不是什么時(shí)候都可以使用的，而是要滿足自身的場(chǎng)景，即目標(biāo)函數(shù)的子問(wèn)題可以用該算法解決，本質(zhì)是分治的思想。

3.遞歸的核心：大事化小，遞歸出口。

main函數(shù)可以遞歸嗎

相信有些讀者就在疑惑啦？main函數(shù)是主函數(shù)呀，這個(gè)怎么可以自己調(diào)用自己呢？

實(shí)際上，main函數(shù)本質(zhì)也是函數(shù)，所以也就會(huì)形成棧幀，所以是可以自己調(diào)用自己的。

代碼和運(yùn)行結(jié)果如下：

int main()
{
	printf("胡楊樹(shù)下\n");
	Sleep(100);//睡眠0.1秒
	main();
	return 0;
}

結(jié)果顯示是可以調(diào)用的，那么我們也能過(guò)看出來(lái)，這個(gè)main函數(shù)的遞歸是不會(huì)自動(dòng)停止的，停止時(shí)就是發(fā)生棧溢出，那么函數(shù)的棧幀是怎么形成的呢？

是最下面的main函數(shù)進(jìn)行調(diào)用自身形成棧幀，如圖示，我們可以看出，這些函數(shù)調(diào)用都開(kāi)辟了空間，所以要占用內(nèi)存，而且形成棧幀后需要釋放，形成和釋放過(guò)程中有時(shí)間消耗。這也就是遞歸有成本的原因。

遞歸核心思想講解

我們?cè)谄綍r(shí)中見(jiàn)過(guò)這個(gè)題目，叫做求字符串長(zhǎng)度。

這個(gè)我們可以用遞歸的寫(xiě)法求解，順帶我們看下遞歸的核心。

首先假設(shè)我們求的字符為 "abcdefg123"，我們用遞歸的解法可以轉(zhuǎn)化為，1+"bcdefg123"，把"bcdefg123"進(jìn)而再轉(zhuǎn)化為1+"cdefg123"，進(jìn)行求解，如圖示：

經(jīng)過(guò)一次次的大事化小，我們最后把問(wèn)題變成了，求1+空字符串的長(zhǎng)度，這個(gè)其實(shí)也就是我們想要的遞歸出口，當(dāng)沒(méi)有字符時(shí)我們就該結(jié)束啦。

代碼如下：

int My_strlen(const char *str)
{
	if (*str == '\0')//函數(shù)出口
	{
		return 0;
	}
	return 1 + My_strlen(str + 1);//繼續(xù)
}
int main()
{
	int len = My_strlen("abcdefg123");
	printf("len = %d\n", len);
	return 0;
}

遞歸的缺點(diǎn)

我們來(lái)看下遞歸的另外一個(gè)經(jīng)典例子，第n個(gè)菲波那切數(shù)列的實(shí)現(xiàn)

首先菲波那切數(shù)列是前兩個(gè)數(shù)之和等于第三個(gè)數(shù)，第一個(gè)和第二個(gè)我們?cè)O(shè)定為1，那么這個(gè)數(shù)列為 1,1,2,3,5,8,13....等等，那我們要求第n個(gè)斐波那契數(shù)列的話，只要轉(zhuǎn)化為求前兩個(gè)數(shù)的和就好了，最后的遞歸出口為第一個(gè)或者第二個(gè)數(shù)時(shí)停止，結(jié)束函數(shù)。

代碼如下：求第十個(gè)菲波那切數(shù)

int fib(int n)
{
	if (n == 1 || n == 2)
	{
		return 1;
	}
	return fib(n - 1) + fib(n - 2);
}
int main()
{
	printf("fib(%d) = %d\n", 10, fib(10));
	return 0;
}

我們?nèi)绻蟮?n 的數(shù)字比較大就會(huì)非常慢。這個(gè)本質(zhì)就是上述說(shuō)的成本問(wèn)題。

如果求的是第42個(gè)菲波那切數(shù)呢？這次我們把時(shí)間也計(jì)算上。

int fib(int n)
{
	if (n == 1 || n == 2)
	{
		return 1;
	}
	return fib(n - 1) + fib(n - 2);
}
int main()
{
	int n = 42;
	double start = GetTickCount();
	int x = fib(n);
	double end = GetTickCount();
	printf("fib(%d) = %d count = %.1f S\n", n,x,(end - start)/1000);
	return 0;
}