前言

在一定的時(shí)間、空間限制下，人的體力有限，思維力也有限，遞歸思維對(duì)實(shí)踐最有用的指導(dǎo)，就是把腦力集中于定義問(wèn)題這個(gè)關(guān)鍵點(diǎn)上，不用去找解題的過(guò)程。定義（問(wèn)題）即解決（問(wèn)題），定義即解決！ 讓大問(wèn)題變成規(guī)模更小的問(wèn)題并立即獲得解決，以此作為基礎(chǔ)，讓我們輕松解決函數(shù)本身定義的問(wèn)題。所以，遞歸在編程中同樣是很重要的一個(gè)知識(shí)點(diǎn)。

提示：以下是本篇文章正文內(nèi)容

一、遞歸是什么？

先來(lái)看一下定義：

程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。

簡(jiǎn)單來(lái)說(shuō)，就是在一個(gè)函數(shù)里面調(diào)用函數(shù)自己本身。

舉個(gè)例子：
用遞歸實(shí)現(xiàn)求第n個(gè)斐波那契數(shù)。

int Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}

int main()
{
	//斐波那契數(shù) 1 1 2 3 5 8 13 21 34 51....,除前兩位外，后一個(gè)數(shù)的值等于前兩位相加
	int n = 0;
	printf("請(qǐng)輸入你要查找的斐波那契數(shù)：");
	scanf("%d", &n);
	int ret=Fib(n);
	printf("你好，你要需要的值是：%d\n", ret);
	return 0;
}

所以，我們可以看到，所謂遞歸，其實(shí)就是一個(gè)函數(shù)里面調(diào)用函數(shù)自己本身。具體怎樣調(diào)用的，我們下面再講。

二、遞歸的兩個(gè)必要條件

1、存在限制條件，當(dāng)滿足這個(gè)限制條件的時(shí)候，遞歸便不再繼續(xù)。
2、每次遞歸調(diào)用之后越來(lái)越接近這個(gè)限制條件。

分析之后，我們可以得出兩個(gè)點(diǎn)

1、結(jié)束條件
2、逼近條件

我們?cè)谑褂眠f歸的時(shí)候，需要滿足這兩個(gè)條件。

總結(jié)起來(lái)四個(gè)字——大事化小

繼續(xù)舉斐波那契數(shù)的例子：

三、遞歸是怎樣運(yùn)行的

我們通過(guò)一道題目來(lái)講解。

題目： 遞歸實(shí)現(xiàn)n的k次方
內(nèi)容： 編寫(xiě)一個(gè)函數(shù)實(shí)現(xiàn)n的k次方，使用遞歸實(shí)現(xiàn)。

【解決思路】
運(yùn)用遞歸思路，我們只要找到遞歸結(jié)束條件和逼近條件。通過(guò)分析，我們可以畫(huà)出下面這幅圖。

【代碼實(shí)現(xiàn)】

#include <stdio.h>
double power(int n,int k)
{
	if (k< 0)
	{
		k = -k;
		return 1 / (n*power(n, k - 1));
	}
	else if (k == 0)
		return 1;
	else if (k>0)
	{
		return n * power(n, k - 1);
	}
}
int main()
{
	int n = 0;
	int k = 0;
	printf("請(qǐng)輸入一個(gè)整數(shù)：");
	scanf("%d", &n);
	printf("請(qǐng)輸入要求的次方數(shù)：");
	scanf("%d", &k);
	double ret=power(n,k);
	printf("%1f\n", ret);
	return 0;
}

【畫(huà)圖詳解遞歸思路】

通過(guò)圖解，發(fā)現(xiàn)思路，我們** 存在限制條件k，當(dāng)滿足這個(gè)限制條件的時(shí)候，遞歸便不再繼續(xù)。
每次遞歸調(diào)用之后越來(lái)越接近這個(gè)限制條件。**之后輸出的時(shí)候就反過(guò)來(lái)回去。

這個(gè)就是遞歸的思路。

四、迭代與遞歸

不知大家有沒(méi)有認(rèn)真思考過(guò)上面的求斐波那契數(shù)的代碼，它有什么問(wèn)題？

如果我們這里求的是第50個(gè)斐波那契數(shù)呢？大家可以運(yùn)行一下代碼?？梢园l(fā)現(xiàn)，電腦運(yùn)行了好久好久才算出結(jié)果，費(fèi)時(shí)間。
如果求第10000個(gè)斐波那契數(shù)呢？程序就會(huì)崩潰。

為什么呢？
我們發(fā)現(xiàn)上面求斐波那契數(shù)的 Fib 函數(shù) 在調(diào)用的過(guò)程中很多計(jì)算其實(shí)在一直重復(fù)。
因?yàn)槲覀冊(cè)谡{(diào)用這個(gè)函數(shù)的時(shí)候，除前兩位外，后一個(gè)數(shù)的值等于前兩位相加。這就導(dǎo)致了我們不斷重復(fù)計(jì)算

如圖：

我們可以看到，由于前兩個(gè)數(shù)相加等于后一個(gè)數(shù)，前兩個(gè)數(shù)相加等于后一個(gè)數(shù)，所以我們會(huì)不斷產(chǎn)生重復(fù)的計(jì)算。就會(huì)造成計(jì)算量非常大，效率極低。

那我們?nèi)绾胃倪M(jìn)呢？
我們程序存東西的時(shí)候，存放在棧區(qū)。
如圖：

在調(diào)試 例子中的Fib函數(shù)的時(shí)候，如果你的參數(shù)比較大，那就會(huì)報(bào)錯(cuò)： `stack overflow（棧溢出） 這樣的信息。
系統(tǒng)分配給程序的?？臻g是有限的，但是如果出現(xiàn)了死循環(huán)，或者（死遞歸），這樣有可能導(dǎo)致一直開(kāi)辟棧空間，最終產(chǎn)生棧空間耗盡的情況，這樣的現(xiàn)象我們稱為棧溢出。

那如何解決上述的問(wèn)題：

將遞歸改寫(xiě)成非遞歸。使用static對(duì)象替代non-static局部對(duì)象。在遞歸函數(shù)設(shè)計(jì)中，可以使用static對(duì)象替代nonstatic局 部對(duì)象（即棧對(duì)象），這不僅可以減少每次遞歸調(diào)用和返回時(shí)產(chǎn)生和釋放nonstatic對(duì)象的開(kāi)銷，
而且static對(duì)象還可以保存遞歸調(diào)用的中間狀態(tài)，并且可為各個(gè)調(diào)用層所訪問(wèn)。

這里我們介紹迭代。

什么是迭代呢？
【概念】

迭代是重復(fù)反饋過(guò)程的活動(dòng)，其目的通常是為了逼近所需目標(biāo)或結(jié)果。每一次對(duì)過(guò)程的重復(fù)稱為一次“迭代”，而每一次迭代得到的結(jié)果會(huì)作為下一次迭代的初始值。

借用網(wǎng)上的圖片來(lái)說(shuō)明（侵刪）

目前對(duì)于c語(yǔ)言來(lái)說(shuō)，迭代可以簡(jiǎn)單認(rèn)為是循環(huán)結(jié)構(gòu)。

那么我們?nèi)绾斡玫姆绞角箪巢瞧鯏?shù)呢？
【代碼如下】

int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n>2)
	{
		c = a + b;//求出c的值
		a = b;//a賦值給b,也就是a作為b的值
		b = c;//b賦值給c，也就是b作為c的值
		n--;
	}
	return c;
}

int main()
{
	// 1 1 2 3 5 8 13 21 34 55,除前兩位外，后一個(gè)數(shù)的值等于前兩位相加
	int n = 0;
	printf("請(qǐng)輸入你要查找的斐波那契數(shù)：");
	scanf("%d", &n);
	int ret = Fib(n);
	printf("你好，你要需要的值是：%d\n", ret);
	return 0;
}

這樣，我們算很大的數(shù)都能一下子算出來(lái)了，雖然不能保證正確，因?yàn)闂Ｒ绯隽?，但是效率很快?/p>

五、遞歸與迭代的比較

我們用一個(gè)表格來(lái)分析：

【注意】

許多問(wèn)題是以遞歸的形式進(jìn)行解釋的，這只是因?yàn)樗确沁f歸的形式更為清晰。但是這些問(wèn)題的迭代實(shí)現(xiàn)往往比遞歸實(shí)現(xiàn)效率更高，雖然代碼的可讀性稍微差些。當(dāng)一個(gè)問(wèn)題相當(dāng)復(fù)雜，難以用迭代實(shí)現(xiàn)時(shí)，此時(shí)遞歸實(shí)現(xiàn)的簡(jiǎn)潔性便可以補(bǔ)償它所帶來(lái)的運(yùn)行時(shí)開(kāi)銷。

六、 什么時(shí)候用遞歸

什么時(shí)候用遞歸呢？

（1）當(dāng)解決一個(gè)問(wèn)題時(shí)，遞歸和非遞歸都可以使用，且沒(méi)有明顯問(wèn)題，那就可以使用遞歸
（2）當(dāng)解決一個(gè)問(wèn)題時(shí)，遞歸寫(xiě)起來(lái)很簡(jiǎn)單，非遞歸比較復(fù)雜，且遞歸沒(méi)有明顯問(wèn)題，那就用遞歸
（3）如果說(shuō)，用遞歸解決問(wèn)題，寫(xiě)起來(lái)簡(jiǎn)單，但是有明顯問(wèn)題，那就不能使用遞歸

最后

以上內(nèi)容是通過(guò)本人學(xué)習(xí)的理解和網(wǎng)上資料的整理梳理出來(lái)的遞歸與迭代的一些內(nèi)容，有錯(cuò)漏之處，還請(qǐng)各位多多包涵與指出，共同進(jìn)步，共同成長(zhǎng)!

到此這篇關(guān)于C語(yǔ)言學(xué)好遞歸看這一篇就夠了的文章就介紹到這了,更多相關(guān)C語(yǔ)言 遞歸內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論