前言

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

提示：以下是本篇文章正文內容

一、遞歸是什么？

先來看一下定義：

程序調用自身的編程技巧稱為遞歸（ recursion）。

簡單來說，就是在一個函數里面調用函數自己本身。

舉個例子：
用遞歸實現求第n個斐波那契數。

int Fib(int n){	if (n <= 2)		return 1;	else		return Fib(n - 1) + Fib(n - 2);}int main(){	//斐波那契數 1 1 2 3 5 8 13 21 34 51....,除前兩位外，后一個數的值等于前兩位相加	int n = 0;	printf("請輸入你要查找的斐波那契數：");	scanf("%d", &n);	int ret=Fib(n);	printf("你好，你要需要的值是：%d/n", ret);	return 0;}

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

二、 遞歸的兩個必要條件

1、存在限制條件，當滿足這個限制條件的時候，遞歸便不再繼續。
2、 每次遞歸調用之后越來越接近這個限制條件。

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

1、結束條件
2、逼近條件

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

總結起來四個字——大事化小

繼續舉斐波那契數的例子：

三、遞歸是怎樣運行的

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

題目： 遞歸實現n的k次方
內容： 編寫一個函數實現n的k次方，使用遞歸實現。

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

【代碼實現】

#include 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("請輸入一個整數：");	scanf("%d", &n);	printf("請輸入要求的次方數：");	scanf("%d", &k);	double ret=power(n,k);	printf("%1f/n", ret);	return 0;}

【畫圖詳解遞歸思路】

通過圖解，發現思路，我們** 存在限制條件k，當滿足這個限制條件的時候，遞歸便不再繼續。
每次遞歸調用之后越來越接近這個限制條件。**之后輸出的時候就反過來回去。

這個就是遞歸的思路。

四、迭代與遞歸

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

如果我們這里求的是第50個斐波那契數呢？大家可以運行一下代碼。可以發現，電腦運行了好久好久才算出結果，費時間。
如果求第10000個斐波那契數呢？程序就會崩潰。

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

如圖：
我們可以看到，由于前兩個數相加等于后一個數，前兩個數相加等于后一個數，所以我們會不斷產生重復的計算。就會造成計算量非常大，效率極低。

那我們如何改進呢？
我們程序存東西的時候，存放在棧區。
如圖：

在調試 例子中的Fib函數的時候，如果你的參數比較大，那就會報錯： `stack overflow（棧溢出） 這樣的信息。
系統分配給程序的棧空間是有限的，但是如果出現了死循環，或者（死遞歸），這樣有可能導致一直開辟棧空間，最終產生棧空間耗盡的情況，這樣的現象我們稱為棧溢出。

那如何解決上述的問題：

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

這里我們介紹迭代。

什么是迭代呢？
【概念】

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

借用網上的圖片來說明（侵刪）

目前對于c語言來說，迭代可以簡單認為是循環結構。

那么我們如何用迭代的方式求斐波那契數呢？
【代碼如下】

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,除前兩位外，后一個數的值等于前兩位相加	int n = 0;	printf("請輸入你要查找的斐波那契數：");	scanf("%d", &n);	int ret = Fib(n);	printf("你好，你要需要的值是：%d/n", ret);	return 0;}

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

五、遞歸與迭代的比較

我們用一個表格來分析：
【注意】

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

六、 什么時候用遞歸

什么時候用遞歸呢？

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

最后

以上內容是通過本人學習的理解和網上資料的整理梳理出來的遞歸與迭代的一些內容，有錯漏之處，還請各位多多包涵與指出，共同進步，共同成長!