前言

最近被函數遞歸困惱許久，今天就帶領大家一起探秘遞歸。

什么是遞歸

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

遞歸做為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接 調用自身的 一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解， 遞歸策略 只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。

遞歸的主要思考方式在于：把大事化小。(這個想法很重要)

遞歸的兩個必要條件

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

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

為了更好的理解遞歸我將為大家分享幾到題目。

題解遞歸

在解題之前，我想剛剛接觸遞歸的小伙伴都會面臨，我知道遞歸是什么，但就是不會寫他或者說不理解怎么實現。為此大家可以參考我的解題三步驟。

步驟一：明確你的函數要實現什么功能。

在我看來，要想求解一個遞歸你肯定要知道你要實現一個什么功能，寫出一大概的函數出來。

//求n的階乘
int demand_factorial(int n)
{
}

在這個代碼中，我們明確了這個函數要求的是n的階乘，求階乘所所需要的參數。

步驟二：尋找遞歸結束的條件

遞歸就是在函數在不斷的調用自己，要想停下來，肯定是要有條件能讓他停下來，不然會一直調用自己而陷入死遞歸。就是說我們要找到一個參數為啥時，遞歸結束，之后直接把結果返回。請注意這個參數值我們必須明白，參數為何值的時候，函數的結果是什么。

對于上面那個例子，我們肯定明白n = 1時函數的結果為1。那么我們便可以這么寫。

//求n的階乘
int demand_factorial(int n)
{
	if (n == 1)
	{
		return 1;
	}
}

為什么說當我們明確知道，n = 1時函數結果我們也知道了，n = 1會為遞歸結束的條件呢。大家可以想我們這個遞歸是要干什么的，不就是求n的階乘嗎，既然我們都知道到n=1的階乘為1了，那么到這里就要結束函數遞歸了。所以說，遞歸結束的條件：可以理解為我們所知道的函數結果的那個參數值，也就是n是一個很小的值。

步驟三：找出函數的等價條件

就是我們要不斷遵循把大事化小的思路，把參數范圍不斷縮小，我們可以通過一些輔助的變量或者操作，使得原函數的結果不變。

例如，demand_factorial（n）這個范圍比較大，我們可以變為demand_factorial（n）=n*

demand_factorial(n-1)，注意n的范圍就變成n-1了，為了讓原函數不變，我們需要讓demand_factorial(n-1)*n.其實，我們就是在為原函數尋找一個等價式。

這一步驟也是最難的大家可以細細體會，下面我們繼續完善代碼。

//求n的階乘
int demand_factorial(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else
	{
		return  demand_factorial(n - 1) * n;
	}
}

大家看完上面的思路可能還是不怎么理解，沒關系，我會帶這個思路繼續為大家分享幾道題目。

• 題目1 strlen的模擬（遞歸實現）

大家繼續按照上面的思路來求解這道題目

1 明確你函數要實現的功能。

假設my_strlen（str）是實現求字符串的長度,代碼如下：

//用遞歸模擬strlen
//str為數組名
int my_strlen(char* str)
{
}

2 找出遞歸結束的條件

我們明白在一個字符串中他的結束標志是'\0'，這時函數結果就是0，所以，很明顯遞歸結束的條件為*str='\0'.代碼如下

//用遞歸模擬strlen
//str為數組名
int my_strlen(char* str)
{
	if (*str == '\0')
	{
		return 0;
	}
}

3 找出函數的等價條件

為了求出字符串的長度，我們肯定是從第一個字符開始數，只到數到我們遞歸結束條件為止。那么該函數的等價為：1+my_strlen(str+1）。其中的my_strlen(str+1)是為了尋找下個字符長度。代碼完善如下：

/用遞歸模擬strlen
//str為數組名
int my_strlen(char* str)
{
	if (*str == '\0')
	{
		return 0;
	}
	else
	{
		return 1 + my_strlen(str + 1);
	}
}

這道題就ok了，大家是否有所體會呢？如果還是不理解我們繼續按照這個模式多加練習。

• 題目2斐波那契數列

斐波那契數列指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……在數學上，斐波那契數列以如下被以遞推的方法定義：F (0)=0， F (1)=1, F (n)= F (n - 1)+ F (n - 2)，求第n項和。

1 明確你函數要實現的功能。

假設fib(n)是實現求第n個斐波那契數，代碼如下:

//求第n個斐波那契數
int fib(int n)
{
}

2 找出遞歸結束的條件

很明顯我們知道當n=1或者n=2的時候斐波那契數都為1，所以，遞歸的結束條件為n<=2,那么函數的返回值便為1.代碼如下：

//求第n個斐波那契數
int fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
}

3 找出函數的等價條件

對于函數的等價條件，題目已經給我們了F (n)= F (n - 1)+ F (n - 2)，所以，代碼完善如下：

//求第n個斐波那契數
int fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		return fib(n - 1) + fib(n + 2);
	}
}

• 題目3 小青蛙跳臺階問題

一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

1 明確你函數要實現的功能

假設 (n) 的功能是求青蛙跳上一個n級的臺階總共有多少種跳法，代碼如下：

//小青蛙跳臺階問題
int jump(int n)
{
}

2 找出遞歸結束的條件

上面說了，求遞歸結束的條件，你直接把 n 范圍變的很小就好，因為 n 越小，我們就越容易直觀著算出 f(n) 的多少，所以當 n = 1時，我們很容易知道f(1) = 1。代碼如下：

//小青蛙跳臺階問題
int jump(int n)
{
	if (n == 1)
	{
		return 1;
	}
}

3 找出函數的等價條件

我們知道青蛙每次跳臺階，可以跳一個臺階，也可以跳二個臺階，所以說青蛙每次跳臺階都有二種跳法。

第一種跳法，第一次跳1個臺階，那么還有n-1個臺階沒跳，剩下的n-1個臺階有jump(n-1)種跳法。

第二種跳法，第一次跳2個臺階，那么還有n-2個臺階沒跳，剩下的n-2個臺階有jump(n-2)種跳法。

所以青蛙所以跳法為：jump(n-1)+jump(n-2)，即等價關系式為：jump(n)=jump(n-1)+jump(n-2)代碼如下

//小青蛙跳臺階問題
int jump(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else
	{
		return jump(n - 1) + jump(n - 2);
	}
}

大家認為上面的代碼對嗎?嘻嘻既然我這么問了，肯定是有問題的了，當我們把代碼運行起來的時候會發現，代碼死遞歸了，這個時候問題肯定就出現在遞歸條件上了，我們的遞歸條件是不嚴謹的。當n=2時，顯然，jump(2)=jump(1)+jump(0),我們知道jump(0)=0，按道理遞歸該結束，但是我們上面代碼的邏輯中會繼續調用jump(0)=jump(-1)+jump(-2),這樣就會導致進入死循環，無限調用。

為了防止出現遞歸結束條件出現不嚴謹的現象，我們每次進行第三步后，應該返回第二步，看根據函數的調用關系會不會出現一些漏掉的一些結束條件。當我們把條件補全，代碼如下：

//小青蛙跳臺階問題
int jump(int n)
{
	if (n <= 2)
	{
		return n;
	}
	else
	{
		return jump(n - 1) + jump(n - 2);
	}
}

今天題目就和大家做到這里了，大家如果還覺的不過癮。我在后面為大家準備了幾道題目大家可以去練習。下面我要繼續為大家分享有關遞歸于迭代的問題。

遞歸與迭代

我想對大家說是并不是所有復雜問題，都可以用遞歸來解決，就算可以也會出現許多問題。我們繼續回到斐波那契數列問題。

//求第n個斐波那契數
int fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		return fib(n - 1) + fib(n + 2);
	}
}

當我們求的第n的比較大的時候，代碼會報錯，stack overflow（棧溢出） 這樣的信息。

系統分配給程序的棧空間是有限的，但是如果出現了死循環，或者（死遞歸），這樣有可能導致一 直開辟棧空間，最終產生棧空間耗盡的情況，這樣的現象我們稱為棧溢出。

為什么說當n很大的時候會，會出現報錯呢？當n=50時，我們來看下面這幅圖。

我們為了求f(50)就要知道f(49)于f(48)以此類推，將會導致出現許多不必要的調用。

當我們修改一下代碼

nt count = 0;//全局變量
int fib(int n)
{
 if(n == 3)
 count++;
 if (n <= 2)         
 return 1;
    else
    return fib(n - 1) + fib(n - 2);
}

會發現count是個很大的值，也就是說f(3)被重復調用了許多次。這樣我們就不難找出當n是個很大的值的時候為什么會報錯了，很明顯這里將會棧溢出。

這里我們用迭代的方法寫一下將會解決棧溢出的問題。

//求第n個斐波那契數
int fib(int n)
{
	int result;
	int pre_result;
	int next_older_result;
	result = pre_result = 1;
	while (n > 2)
	{
		n -= 1;
		next_older_result = pre_result;
		pre_result = result;
		result = pre_result + next_older_result;
	}
	return result;
}

總結：

1我們在用遞歸的時候是為了更好的解決問題，因為他形式更加清晰

2當發現遞歸會出現棧溢出的現象時不妨換用迭代的方式解決。

練習題

• 題目1打印一個數的每一位

類容：

遞歸方式實現打印一個整數的每一位

• 題目2字符串逆序（遞歸實現）

類容：

編寫一個函數 reverse_string(char * string)（遞歸實現）

實現：將參數字符串中的字符反向排列，不是逆序打印。

要求：不能使用C函數庫中的字符串操作函數。

比如:

char arr[] = "abcdef";

逆序之后數組的內容變成：fedcba

• 題目3遞歸實現n的k次方

內容：

編寫一個函數實現n的k次方，使用遞歸實現。

• 題目4漢諾塔問題

內容：

相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置64個金盤(如圖1)。游戲的目標：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好。操作規則：每次只能移動一個盤子，并且在移動過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于A、B、C任一桿上。請用遞歸實現。

結束語

遞歸還是挺難的，大家還是要做幾到題目，不理解的地方還可以畫圖理解。