一、什么是遞歸

程序調(diào)用自身的編程技巧稱為遞歸( recursion) 。遞歸做為一種算法在程序設(shè)計語言中廣泛應(yīng)用。一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法,它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解,遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算,大大地減少了程序的代碼量。遞歸的主要思考方式在于:把大事化小

遞歸的兩個必要條件：

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

int main()
{
	printf("hehe\n");
	main();
	return 0;
}

函數(shù)自己調(diào)用自己，一直打印 “hehe” 但是一會程序自己會停下來。這不是真正的遞歸，是一個死循環(huán)（不滿住遞歸的兩個條件）

遞歸實現(xiàn)：接收一個整型值（無符號），按照順序打印它的每一位。

例如：

輸入：1234

輸出：4321

void print(unsigned int n)
{
	if (n > 9)
	{
		print(n / 10);
	}
	printf("%d", n % 10);
}
int main()
{
	unsigned int num = 0;
	scanf("%u", &num);
	//遞歸-函數(shù)自己調(diào)用自己
	print(num);
	return 0;
}

基本的實現(xiàn)邏輯如圖：

寫遞歸代碼的時候注意：

• 不能死遞歸，都有跳出條件，每次遞歸逼近跳出條件
• 遞歸層次不能太深（可能會棧溢出）

二、遞歸與迭代

求第n個斐波那契數(shù)，（可以遞歸實現(xiàn)也可以迭代實現(xiàn)）(不考慮溢出)
我們知道像：1，1，2，3，5，8，13，21，34…… 這樣第n個數(shù)等于第n-1個數(shù)加上n-2個數(shù)的和的一個數(shù)列就是斐波那契數(shù)列

• 遞歸實現(xiàn)求斐波那契數(shù)，直接看代碼：

int Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}
int main()
{
	int n = 0;
	scanf("%d",&n);
	int ret = Fib(n);
	printf("%d\n", ret);
	return 0;
}

當(dāng)我們求很小的斐波那契數(shù)時，計算機(jī)計算很快。但是當(dāng)我們要求的一個很大的，比如第50個斐波那契數(shù)，計算機(jī)就會算很久（大概要五分鐘）。大家可以試一試。

為什么會這么慢呢。因為遞歸實現(xiàn)效率太低，要重復(fù)大量的計算（計算層次太多）。

代碼實現(xiàn)的基本邏輯如圖：

我們可以看一下代碼在計算過程中 n=3（計算第三個斐波那契數(shù)） 這一步要執(zhí)行的次數(shù)：

在計算第40個斐波那契數(shù)時，要計算三千多萬次第三個斐波那契數(shù)。可想而知遞歸實現(xiàn)的效率有多低。而且計算太大還會造成程序崩潰。

• 循環(huán)迭代實現(xiàn)求斐波那契數(shù)，直接看代碼：

int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d\n", ret);
	return 0;
}

循環(huán)迭代的方式計算很快

提示：

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

到此這篇關(guān)于C語言函數(shù)的遞歸調(diào)用詳情的文章就介紹到這了,更多相關(guān)C語言遞歸調(diào)用內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論