什么是遞歸？

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

如何理解函數(shù)遞歸：

1.從調(diào)用自身層面：函數(shù)遞歸就是函數(shù)自己調(diào)用自己。

2.從編程技巧層面：一種方法（把一個大型復(fù)雜的程序轉(zhuǎn)換為一個類似的小型簡單的程序），這種方法的主要思想就是把大事化小。

遞歸的兩個必要條件

1.存在限制條件，當(dāng)滿足這個限制條件時，遞歸便不再繼續(xù)。

2.每次遞歸調(diào)用之后越來越接近這個限制條件。

遞歸實例

實例1（按照順序打印一個數(shù)的整形值）

參考代碼（可以先去嘗試是否可以解決問題）

畫圖講解 

注意：在每次打印后都有一個空格。

程序運行結(jié)果

完整代碼 

#include <stdio.h>
void print(int n)
{
if(n>9)
{
print(n/10);
}
printf("%d ", n%10);
}
int main()
{
int num = 1234;
print(num);
return 0;
}

實例2 （使用函數(shù)在不創(chuàng)建變量的情況下求字符串長度）

參考代碼

畫圖講解

程序運行結(jié)果

完整代碼

#include <stdio.h>int Strlen(const char* str){if (*str == '\0')return 0;elsereturn 1 + Strlen(str + 1);}int main(){char* p = "abcd";int len = Strlen(p);printf("%d\n", len);return 0;}

遞歸與迭代

迭代是重復(fù)反饋過程的活動，其目的通常是為了逼近所需目標(biāo)或結(jié)果。 每一次對過程的重復(fù)稱為一次“迭代”，而每一次迭代得到的結(jié)果會作為下一次迭代的初始值。 目前對于c語言來說，迭代可以簡單認(rèn)為是循環(huán)結(jié)構(gòu)。

對于遞歸與迭代，我們同樣通過兩個實例來理解：

實例1 （求n的階乘）

方法一（使用遞歸）

參考代碼

通過數(shù)學(xué)方法講解

完整代碼 

#include <stdio.h>
int fac(int n)
{
	if (n == 1)
		return 1;
	else
		return n * fac(n - 1);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = fac(n);
	printf("%d\n", ret);
	return 0;
}

方法二（使用迭代）

完整代碼

#include <stdio.h>
int main()
{
	int n = 0;
	scanf("%d", &n);
	int i = 0;
	int ret = 1;
	for (i = 1; i <= n; i++)
	{
		ret *= i;
	}
	printf("%d\n", ret);
	return 0;
}

 運行結(jié)果

實例2 （求解斐波那契數(shù)列）

斐波那契數(shù)列：指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F(1)=1，F(xiàn)(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）

方法一 （遞歸求解）

 參考代碼

通過數(shù)學(xué)方法求解 

運行結(jié)果  

完整代碼 

#include <stdio.h>
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ù)字較大時，使用遞歸的方法計算機所要計算的量是相當(dāng)大的，因為每次計算一個第n項時都需要計算第n-1項和第n-2項 ，這里我們通過求解第40項來觀察fib(3)的計算次數(shù)來觀察。

運行結(jié)果

計算第40項時已經(jīng)計算第3項已經(jīng)有三千多萬次，那么如果計算第一百項，一千項...時程序就會崩潰...這是我們就要考慮使用迭代的方法進(jìn)行求解。

方法二（迭代求解） 

參考代碼 （主函數(shù)不變）

畫圖講解 

完整代碼 

#include <stdio.h>
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;
}

運行結(jié)果 

這里我們可以看出遞歸和迭代的運行結(jié)果是一樣的，但是迭代的運行速度要更快。 

這時候我們會想：

為什么有時候用遞歸簡便，而有時候用迭代簡便呢？

注意：

1.許多問題是以遞歸的形式進(jìn)行求解的，這只是因為它比非遞歸的形式更加清晰。

2.但是這些問題的迭代實現(xiàn)往往比遞歸實現(xiàn)效率更高，雖然可讀性差些。

3.當(dāng)一個問題相當(dāng)復(fù)雜時，此時遞歸實現(xiàn)的簡潔性便可以彌補它所帶來的運行開銷。

總結(jié)

本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!    

最新評論