前言

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

什么是遞歸

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

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

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

遞歸的兩個必要條件

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

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

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

題解遞歸

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

步驟一：明確你的函數要實現(xiàn)什么功能。

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

//求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）這個范圍比較大，我們可以變?yōu)閐emand_factorial（n）=n*

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

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

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

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

• 題目1 strlen的模擬（遞歸實現(xiàn)）

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

1 明確你函數要實現(xiàn)的功能。

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

//用遞歸模擬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了，大家是否有所體會呢？如果還是不理解我們繼續(xù)按照這個模式多加練習。

• 題目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 明確你函數要實現(xiàn)的功能。

假設fib(n)是實現(xià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 明確你函數要實現(xiàn)的功能

假設 (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);
	}
}

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

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

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

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

遞歸與迭代

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

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

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

系統(tǒng)分配給程序的棧空間是有限的，但是如果出現(xiàn)了死循環(huán)，或者（死遞歸），這樣有可能導致一 直開辟棧空間，最終產生?？臻g耗盡的情況，這樣的現(xiàn)象我們稱為棧溢出。

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

我們?yōu)榱饲骹(50)就要知道f(49)于f(48)以此類推，將會導致出現(xiàn)許多不必要的調用。

當我們修改一下代碼

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

會發(fā)現(xiàn)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當發(fā)現(xiàn)遞歸會出現(xiàn)棧溢出的現(xiàn)象時不妨換用迭代的方式解決。

練習題

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

類容：

遞歸方式實現(xiàn)打印一個整數的每一位

• 題目2字符串逆序（遞歸實現(xiàn)）

類容：

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

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

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

比如:

char arr[] = "abcdef";

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

• 題目3遞歸實現(xiàn)n的k次方

內容：

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

• 題目4漢諾塔問題

內容：

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

結束語

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

到此這篇關于C語言超細致講解函數遞歸的文章就介紹到這了,更多相關C語言函數遞歸內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論