函數(shù)遞歸

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

函數(shù)自己調(diào)用自己就是遞歸

你也可以理解成是一種嵌套結(jié)構(gòu)，但遞歸分為倆部分，第一是“遞”，進(jìn)入嵌套結(jié)構(gòu)。第二是”歸“，最終會(huì)一步一步返回。第一次接觸遞歸都會(huì)很懵，慢慢理解這個(gè)過(guò)程就明白了。

什么是遞歸？

遞歸做為一種算法在程序設(shè)計(jì)語(yǔ)言中廣泛應(yīng)用。 一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中有直接或間接調(diào)用自身的一種方法，它通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，

遞歸策略只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。

遞歸的主要思考方式在于：把大事化小

遞歸的倆個(gè)必要條件

代碼引例1

接受一個(gè)整型值（無(wú)符號(hào)），按照順序打印它的每一位。

例如：

輸入：123，輸出 1 2 3

參考代碼：

#include <stdio.h>
void print(int n) {
 if(n>9)
 {
 print(n/10);
 }
 printf("%d ", n%10);
}
int main()
{
 int num = 123;
 print(num);
 return 0; }

運(yùn)行結(jié)果如下：

我們要怎么理解這個(gè)函數(shù)遞歸的實(shí)現(xiàn)呢

我們可以采用畫(huà)圖方式理解這個(gè)過(guò)程

所以我們可以看到，遞歸必須滿足倆個(gè)必要條件：

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

2.每次遞歸調(diào)用之后越來(lái)越接近這個(gè)限制條件。

題中的限制條件就是（n>9),當(dāng)我們的n通過(guò)（n/10)越來(lái)越少，直至n=1，無(wú)法滿足時(shí)，遞歸停止，并開(kāi)始返回。

這里有一個(gè)重要點(diǎn)就是print（n/10),如果沒(méi)有這個(gè)條件，換成print（n）的話，n一直無(wú)法減小，一直進(jìn)行遞歸。最后會(huì)導(dǎo)致棧溢出(Stack Overflow)。

棧溢出（Stack Overflow）

關(guān)于棧溢出，我就先簡(jiǎn)單介紹一下棧

棧：棧是一種計(jì)算機(jī)系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)，它按照先進(jìn)后出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開(kāi)始彈出數(shù)據(jù)（最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來(lái)），是一種特殊的線性表。棧的操作常用的有進(jìn)棧（PUSH），出棧（POP），還有常用的標(biāo)識(shí)棧頂和棧底。

可以把棧想象成一摞撲克牌一樣，一張一張疊加起來(lái)。

而棧溢出呢是緩沖區(qū)溢出的一種，緩沖區(qū)溢出：簡(jiǎn)單的說(shuō)，緩沖區(qū)溢出就是超長(zhǎng)的數(shù)據(jù)向小緩沖區(qū)復(fù)制，導(dǎo)致數(shù)據(jù)超出了小緩沖區(qū)，導(dǎo)致緩沖區(qū)其他的數(shù)據(jù)遭到破壞，這就是緩沖區(qū)溢出。而棧溢出是緩沖區(qū)溢出的一種，也是最常見(jiàn)的。只不過(guò)棧溢出發(fā)生在棧，堆溢出發(fā)生在堆，其實(shí)都是一樣的。

而在代碼引例1中

系統(tǒng)分配給程序的棧空間是有限的，但是如果出現(xiàn)了死循環(huán)，或者（死遞歸），這樣有可能導(dǎo)致一

直開(kāi)辟?？臻g，最終產(chǎn)生?？臻g耗盡的情況，這樣的現(xiàn)象我們稱(chēng)為棧溢出

合理使用遞歸

使用遞歸的宗旨是把大事化小

所以遇到問(wèn)題時(shí)，我們應(yīng)該明白是要把問(wèn)題簡(jiǎn)單化，而不是習(xí)慣用遞歸，就一直用遞歸思考問(wèn)題

我們應(yīng)該清楚是不是用遞歸的思想會(huì)比較簡(jiǎn)單，或者換成遞歸的思想也可以實(shí)現(xiàn)，我們可以通過(guò)例題明白

代碼引例3

求n的階乘

用循環(huán)的方法，代碼如下：

int main()
{
	int n = 0;
	int ret = 1;
	scanf("%d", &n);
	//循環(huán)產(chǎn)生1~n的數(shù)字
	int i = 0;
	for (i = 1; i <= n; i++)
	{
		ret = ret * i;
	}
	printf("ret = %d\n", ret);

	return 0;
}

而采用遞歸的話，代碼如下：

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("%d\n", ret);
	return 0;
}

很多人剛學(xué)遞歸，都是懂了，但不知道怎么用。

而這道題可以先用公式來(lái)理解題目，再來(lái)用遞歸就容易多了

再來(lái)對(duì)比一下函數(shù)的代碼，是不是清晰明了呢

代碼引例4

求第n個(gè)斐波那契數(shù)。（不考慮溢出）

代碼如下：

int fib(int n) {
 if (n <= 2)         
 return 1;
    else
    return fib(n - 1) + fib(n - 2);
}

這道題同樣我們也可以利用公式構(gòu)造一個(gè)函數(shù)實(shí)現(xiàn)遞歸

具體思路如下：

解釋要合理使用遞歸

通過(guò)以上倆個(gè)例題，我們可以發(fā)現(xiàn)倆個(gè)問(wèn)題：

在使用 fib 這個(gè)函數(shù)的時(shí)候如果我們要計(jì)算第50個(gè)斐波那契數(shù)字的時(shí)候特別耗費(fèi)時(shí)間。

使用 factorial 函數(shù)求10000的階乘（不考慮結(jié)果的正確性），程序會(huì)崩潰。

為什么呢？

我們發(fā)現(xiàn) fib 函數(shù)在調(diào)用的過(guò)程中很多計(jì)算其實(shí)在一直重復(fù)。

如果我們把代碼修改一下：

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

最后我們輸出看看count，是一個(gè)很大很大的值。

那我們?nèi)绾胃倪M(jìn)呢？

在調(diào)試 factorial 函數(shù)的時(shí)候，如果你的參數(shù)比較大，那就會(huì)報(bào)錯(cuò)： stack overflow（棧溢出）

這樣的信息。

那如何解決上述的問(wèn)題：

1.將遞歸改寫(xiě)成非遞歸。

2.使用static對(duì)象替代 nonstatic 局部對(duì)象。在遞歸函數(shù)設(shè)計(jì)中，可以使用 static 對(duì)象替代

nonstatic 局部對(duì)象（即棧對(duì)象），這不僅可以減少每次遞歸調(diào)用和返回時(shí)產(chǎn)生和釋放 nonstatic 對(duì)象的開(kāi)銷(xiāo)，而且 static 對(duì)象還可以保存遞歸調(diào)用的中間狀態(tài)，并且可為各個(gè)調(diào)用層所訪問(wèn)

比如，下面代碼就采用了，非遞歸的方式來(lái)實(shí)現(xiàn)：

//求n的階乘
int factorial(int n) {
        int result = 1;
        while (n > 1)
       {
             result *= n ;
             n -= 1;
       }
        return result; }
//求第n個(gè)斐波那契數(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; 
     }

提示：

1.許多問(wèn)題是以遞歸的形式進(jìn)行解釋的，這只是因?yàn)樗确沁f歸的形式更為清晰。

2.但是這些問(wèn)題的迭代實(shí)現(xiàn)往往比遞歸實(shí)現(xiàn)效率更高，雖然代碼的可讀性稍微差些。

3.當(dāng)一個(gè)問(wèn)題相當(dāng)復(fù)雜，難以用迭代實(shí)現(xiàn)時(shí)，此時(shí)遞歸實(shí)現(xiàn)的簡(jiǎn)潔性便可以補(bǔ)償它所帶來(lái)的運(yùn)行時(shí)開(kāi)銷(xiāo)

總結(jié)

本篇文章就到這里了，希望能夠給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

最新評(píng)論