一篇文章帶你瞭解C語言函數遞迴

2022-02-08 19:00:53

什麼是遞迴？

遞迴（recursion）：程式呼叫自身的一種程式設計技巧。

如何理解函數遞迴：

1.從呼叫自身層面：函數遞迴就是函數自己呼叫自己。

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

遞迴的兩個必要條件

1.存在限制條件，當滿足這個限制條件時，遞迴便不再繼續。

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 （使用函數在不建立變數的情況下求字串長度）

參考程式碼

畫圖講解

程式執行結果

完整程式碼

#include &lt;stdio.h&gt;int Strlen(const char* str){if (*str == '')return 0;elsereturn 1 + Strlen(str + 1);}int main(){char* p = "abcd";int len = Strlen(p);printf("%dn", len);return 0;}

遞迴與迭代

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

對於遞迴與迭代，我們同樣通過兩個範例來理解：

範例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("%dn", 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("%dn", 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("%dn", 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("%dn", ret);
	return 0;
}

執行結果

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

這時候我們會想：

為什麼有時候用遞迴簡便，而有時候用迭代簡便呢？

注意：

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

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

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

總結

本篇文章就到這裡了，希望能夠給你帶來幫助，也希望您能夠多多關注it145.com的更多內容!

一篇文章帶你瞭解C語言函數遞迴

目錄

什麼是遞迴？

遞迴的兩個必要條件

遞迴範例

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

畫圖講解

完整程式碼

範例2 （使用函數在不建立變數的情況下求字串長度）

畫圖講解

程式執行結果

完整程式碼

遞迴與迭代

範例1 （求n的階乘）

方法一（使用遞迴）

方法二（使用迭代）

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

方法一（遞迴求解）

方法二（迭代求解）

總結

熱門文章

一篇文章帶你瞭解C語言函數遞迴

目錄

什麼是遞迴？

遞迴的兩個必要條件

遞迴範例

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

畫圖講解

完整程式碼

範例2 （使用函數在不建立變數的情況下求字串長度）

畫圖講解

程式執行結果

完整程式碼

遞迴與迭代

範例1 （求n的階乘）

方法一（使用遞迴）

方法二（使用迭代）

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

方法一 （遞迴求解）

方法二（迭代求解）

總結

熱門文章

方法一（遞迴求解）