前言

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

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

一、遞歸是什么？

先來看一下定義：

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

簡單來說，就是在一個函數(shù)里面調(diào)用函數(shù)自己本身。

舉個例子：
用遞歸實現(xiàn)求第n個斐波那契數(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....,除前兩位外，后一個數(shù)的值等于前兩位相加
	int n = 0;
	printf("請輸入你要查找的斐波那契數(shù)：");
	scanf("%d", &n);
	int ret=Fib(n);
	printf("你好，你要需要的值是：%d\n", ret);
	return 0;
}

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

二、遞歸的兩個必要條件

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

分析之后，我們可以得出兩個點

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

我們在使用遞歸的時候，需要滿足這兩個條件。

總結(jié)起來四個字——大事化小

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

三、遞歸是怎樣運行的

我們通過一道題目來講解。

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

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

【代碼實現(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("請輸入一個整數(shù)：");
	scanf("%d", &n);
	printf("請輸入要求的次方數(shù)：");
	scanf("%d", &k);
	double ret=power(n,k);
	printf("%1f\n", ret);
	return 0;
}

【畫圖詳解遞歸思路】

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

這個就是遞歸的思路。

四、迭代與遞歸

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

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

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

如圖：

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

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

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

那如何解決上述的問題：

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

這里我們介紹迭代。

什么是迭代呢？
【概念】

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

借用網(wǎng)上的圖片來說明（侵刪）

目前對于c語言來說，迭代可以簡單認(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,除前兩位外，后一個數(shù)的值等于前兩位相加
	int n = 0;
	printf("請輸入你要查找的斐波那契數(shù)：");
	scanf("%d", &n);
	int ret = Fib(n);
	printf("你好，你要需要的值是：%d\n", ret);
	return 0;
}

這樣，我們算很大的數(shù)都能一下子算出來了，雖然不能保證正確，因為棧溢出了，但是效率很快。

五、遞歸與迭代的比較

我們用一個表格來分析：

【注意】

許多問題是以遞歸的形式進(jìn)行解釋的，這只是因為它比非遞歸的形式更為清晰。但是這些問題的迭代實現(xiàn)往往比遞歸實現(xiàn)效率更高，雖然代碼的可讀性稍微差些。當(dāng)一個問題相當(dāng)復(fù)雜，難以用迭代實現(xiàn)時，此時遞歸實現(xiàn)的簡潔性便可以補償它所帶來的運行時開銷。

六、 什么時候用遞歸

什么時候用遞歸呢？

（1）當(dāng)解決一個問題時，遞歸和非遞歸都可以使用，且沒有明顯問題，那就可以使用遞歸
（2）當(dāng)解決一個問題時，遞歸寫起來很簡單，非遞歸比較復(fù)雜，且遞歸沒有明顯問題，那就用遞歸
（3）如果說，用遞歸解決問題，寫起來簡單，但是有明顯問題，那就不能使用遞歸

最后

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

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

最新評論