遞歸的認識

基本認識：

1.首先遞歸的本質還是函數調用，也要形成和釋放棧幀。

2.函數的調用是有成本的，這個成本在時間和空間上表現為函數棧幀的形成和銷毀。

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

理論認識：

1.內存和cpu中的資源有限，也就決定啦，合理的遞歸是絕對不可以無限遞歸下去的。

2.遞歸不是什么時候都可以使用的，而是要滿足自身的場景，即目標函數的子問題可以用該算法解決，本質是分治的思想。

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

main函數可以遞歸嗎

相信有些讀者就在疑惑啦？main函數是主函數呀，這個怎么可以自己調用自己呢？

實際上，main函數本質也是函數，所以也就會形成棧幀，所以是可以自己調用自己的。

代碼和運行結果如下：

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

結果顯示是可以調用的，那么我們也能過看出來，這個main函數的遞歸是不會自動停止的，停止時就是發生棧溢出，那么函數的棧幀是怎么形成的呢？

是最下面的main函數進行調用自身形成棧幀，如圖示，我們可以看出，這些函數調用都開辟了空間，所以要占用內存，而且形成棧幀后需要釋放，形成和釋放過程中有時間消耗。這也就是遞歸有成本的原因。

遞歸核心思想講解

我們在平時中見過這個題目，叫做求字符串長度。

這個我們可以用遞歸的寫法求解，順帶我們看下遞歸的核心。

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

經過一次次的大事化小，我們最后把問題變成了，求1+空字符串的長度，這個其實也就是我們想要的遞歸出口，當沒有字符時我們就該結束啦。

代碼如下：

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

遞歸的缺點

我們來看下遞歸的另外一個經典例子，第n個菲波那切數列的實現

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

代碼如下：求第十個菲波那切數

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 的數字比較大就會非常慢。這個本質就是上述說的成本問題。

如果求的是第42個菲波那切數呢？這次我們把時間也計算上。

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;
}

我們可以看出第42個時就已經10秒了，這個很長時間啦。我們用全局變量接收下次數，那我們看看他計算了多少次第3個菲波那切數計算了幾次？ 計算了大概1億多次，所以遞歸的重

復計算是非常多的。

我們看個圖示：

其中單單是第六個菲波那切數就計算了3次，這個就很夸張啦。

所以遞歸的特點是代碼簡單，但是調用上可能會有大的成本。

最后一點就是：循環和遞歸是一定可以相互轉化的。只不過有些時候轉化會比較麻煩。