函數(shù)遞歸

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

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

你也可以理解成是一種嵌套結構，但遞歸分為倆部分，第一是“遞”，進入嵌套結構。第二是”歸“，最終會一步一步返回。第一次接觸遞歸都會很懵，慢慢理解這個過程就明白了。

什么是遞歸？

遞歸做為一種算法在程序設計語言中廣泛應用。 一個過程或函數(shù)在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規(guī)模較小的問題來求解，

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

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

遞歸的倆個必要條件

代碼引例1

接受一個整型值（無符號），按照順序打印它的每一位。

例如：

輸入：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; }

運行結果如下：

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

我們可以采用畫圖方式理解這個過程

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

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

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

題中的限制條件就是（n>9),當我們的n通過（n/10)越來越少，直至n=1，無法滿足時，遞歸停止，并開始返回。

這里有一個重要點就是print（n/10),如果沒有這個條件，換成print（n）的話，n一直無法減小，一直進行遞歸。最后會導致棧溢出(Stack Overflow)。

棧溢出（Stack Overflow）

關于棧溢出，我就先簡單介紹一下棧

棧：棧是一種計算機系統(tǒng)中的數(shù)據(jù)結構，它按照先進后出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來），是一種特殊的線性表。棧的操作常用的有進棧（PUSH），出棧（POP），還有常用的標識棧頂和棧底。

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

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

而在代碼引例1中

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

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

合理使用遞歸

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

所以遇到問題時，我們應該明白是要把問題簡單化，而不是習慣用遞歸，就一直用遞歸思考問題

我們應該清楚是不是用遞歸的思想會比較簡單，或者換成遞歸的思想也可以實現(xiàn)，我們可以通過例題明白

代碼引例3

求n的階乘

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

int main()
{
	int n = 0;
	int ret = 1;
	scanf("%d", &n);
	//循環(huá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;
}

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

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

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

代碼引例4

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

代碼如下：

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

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

具體思路如下：

解釋要合理使用遞歸

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

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

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

為什么呢？

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

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

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，是一個很大很大的值。

那我們如何改進呢？

在調試 factorial 函數(shù)的時候，如果你的參數(shù)比較大，那就會報錯： stack overflow（棧溢出）

這樣的信息。

那如何解決上述的問題：

1.將遞歸改寫成非遞歸。

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

nonstatic 局部對象（即棧對象），這不僅可以減少每次遞歸調用和返回時產生和釋放 nonstatic 對象的開銷，而且 static 對象還可以保存遞歸調用的中間狀態(tài)，并且可為各個調用層所訪問

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

//求n的階乘
int factorial(int n) {
        int result = 1;
        while (n > 1)
       {
             result *= n ;
             n -= 1;
       }
        return result; }
//求第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; 
     }

提示：

1.許多問題是以遞歸的形式進行解釋的，這只是因為它比非遞歸的形式更為清晰。

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

3.當一個問題相當復雜，難以用迭代實現(xiàn)時，此時遞歸實現(xiàn)的簡潔性便可以補償它所帶來的運行時開銷

總結

本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關注腳本之家的更多內容!

最新評論