什么是遞歸？

遞歸（recursion）：程序調用自身的一種編程技巧。

如何理解函數遞歸：

1.從調用自身層面：函數遞歸就是函數自己調用自己。

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

遞歸的兩個必要條件

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

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

遞歸實例

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

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

畫圖講解 

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

程序運行結果

完整代碼 

#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 （使用函數在不創(chuàng)建變量的情況下求字符串長度）

參考代碼

畫圖講解

程序運行結果

完整代碼

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

遞歸與迭代

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

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

實例1 （求n的階乘）

方法一（使用遞歸）

參考代碼

通過數學方法講解

完整代碼 

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

 運行結果

實例2 （求解斐波那契數列）

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

方法一 （遞歸求解）

 參考代碼

通過數學方法求解 

運行結果  

完整代碼 

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

注意：當求得的數字較大時，使用遞歸的方法計算機所要計算的量是相當大的，因為每次計算一個第n項時都需要計算第n-1項和第n-2項 ，這里我們通過求解第40項來觀察fib(3)的計算次數來觀察。

運行結果

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

方法二（迭代求解） 

參考代碼 （主函數不變）

畫圖講解 

完整代碼 

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

運行結果 

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

這時候我們會想：

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

注意：

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

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

3.當一個問題相當復雜時，此時遞歸實現的簡潔性便可以彌補它所帶來的運行開銷。

總結

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

最新評論