快捷導(dǎo)航

C語言超細(xì)致講解函數(shù)遞歸

更新時間：2022年05月11日 14:58:35 作者：^O^玩轉(zhuǎn)編程

程序調(diào)???的編程技巧稱為遞歸?recursion）函數(shù)??調(diào)???就是遞歸，你也可以理解成是?種嵌套結(jié)構(gòu)，但遞歸分為倆部分，第?是“遞”，進(jìn)?嵌套結(jié)構(gòu)。第?是”歸“，最終會?步?步返回。第?次接觸遞歸都會很懵，慢慢理解這個過程就明?了

前言

最近被函數(shù)遞歸困惱許久，今天就帶領(lǐng)大家一起探秘遞歸。

什么是遞歸

程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。

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

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

遞歸的兩個必要條件

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

2 每次遞歸調(diào)用之后越來越接近這個限制條件

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

題解遞歸

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

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

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

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

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

步驟二：尋找遞歸結(jié)束的條件

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

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

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

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

步驟三：找出函數(shù)的等價條件

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

例如，demand_factorial（n）這個范圍比較大，我們可以變?yōu)閐emand_factorial（n）=n*

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

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

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

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

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

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

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

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

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

2 找出遞歸結(jié)束的條件

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

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

3 找出函數(shù)的等價條件

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

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

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

題目2斐波那契數(shù)列

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

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

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

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

2 找出遞歸結(jié)束的條件

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

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

3 找出函數(shù)的等價條件

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

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

題目3 小青蛙跳臺階問題

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

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

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

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

2 找出遞歸結(jié)束的條件

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

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

3 找出函數(shù)的等價條件

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

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

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

所以青蛙所以跳法為：jump(n-1)+jump(n-2)，即等價關(guān)系式為：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);
	}
}

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

為了防止出現(xiàn)遞歸結(jié)束條件出現(xiàn)不嚴(yán)謹(jǐn)?shù)默F(xiàn)象，我們每次進(jìn)行第三步后，應(yīng)該返回第二步，看根據(jù)函數(shù)的調(diào)用關(guān)系會不會出現(xiàn)一些漏掉的一些結(jié)束條件。當(dāng)我們把條件補(bǔ)全，代碼如下：

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

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

遞歸與迭代

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

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

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

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

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

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

當(dāng)我們修改一下代碼

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)被重復(fù)調(diào)用了許多次。這樣我們就不難找出當(dāng)n是個很大的值的時候為什么會報錯了，很明顯這里將會棧溢出。

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

//求第n個斐波那契數(shù)
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;
}

總結(jié)：

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

2當(dāng)發(fā)現(xiàn)遞歸會出現(xiàn)棧溢出的現(xiàn)象時不妨換用迭代的方式解決。

練習(xí)題

題目1打印一個數(shù)的每一位

類容：

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

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

類容：

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

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

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

比如:

char arr[] = "abcdef";

逆序之后數(shù)組的內(nèi)容變成：fedcba

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

內(nèi)容：

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

題目4漢諾塔問題

內(nèi)容：

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