第C語言超細(xì)致講解函數(shù)遞歸目錄前言什么是遞歸遞歸的兩個必要條件題解遞歸遞歸與迭代練習(xí)題結(jié)束語

前言

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

什么是遞歸

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

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

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

遞歸的兩個必要條件

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

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

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

題解遞歸

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

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

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

//求n的階乘

intdemand_factorial(intn)

}

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

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

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

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

//求n的階乘

intdemand_factorial(intn)

if(n==1)

return1;

}

為什么說當(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í)，我們就是在為原函數(shù)尋找一個等價式。

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

//求n的階乘

intdemand_factorial(intn)

if(n==1)

return1;

else

returndemand_factorial(n-1)*n;

}

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

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

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

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

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

//用遞歸模擬strlen

//str為數(shù)組名

intmy_strlen(char*str)

}

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

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

//用遞歸模擬strlen

//str為數(shù)組名

intmy_strlen(char*str)

if(*str=='\0')

return0;

}

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

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

/用遞歸模擬strlen

//str為數(shù)組名

intmy_strlen(char*str)

if(*str=='\0')

return0;

else

return1+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(xiàn)(1)=1,F(n)=F(n-1)+F(n-2)，求第n項(xiàng)和。

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

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

//求第n個斐波那契數(shù)

intfib(intn)

}

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

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

//求第n個斐波那契數(shù)

intfib(intn)

if(n=2)

return1;

}

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

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

//求第n個斐波那契數(shù)

intfib(intn)

if(n=2)

return1;

else

returnfib(n-1)+fib(n+2);

}

題目3小青蛙跳臺階問題

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

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

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

//小青蛙跳臺階問題

intjump(intn)

}

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

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

//小青蛙跳臺階問題

intjump(intn)

if(n==1)

return1;

}

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)代碼如下

//小青蛙跳臺階問題

intjump(intn)

if(n==1)

return1;

else

returnjump(n-1)+jump(n-2);

}

大家認(rèn)為上面的代碼對嗎嘻嘻既然我這么問了，肯定是有問題的了，當(dāng)我們把代碼運(yùn)行起來的時候會發(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ǔ)全，代碼如下：

//小青蛙跳臺階問題

intjump(intn)

if(n=2)

returnn;

else

returnjump(n-1)+jump(n-2);

}

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

遞歸與迭代

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

//求第n個斐波那契數(shù)

intfib(intn)

if(n=2)

return1;

else

returnfib(n-1)+fib(n+2);

}

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

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

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

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

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

ntcount=0;//全局變量

intfib(intn)

if(n==3)

count++;

if(n=2)

return1;

else

returnfib(n-1)+fib(n-2);

}

會發(fā)現(xiàn)count是個很大的值，也就是說f(3)被重復(fù)調(diào)用了許多次。這樣我們就不難找出當(dāng)n是個很大的值的時候?yàn)槭裁磿?bào)錯了，很明顯這里將會棧溢出。

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

//求第n個斐波那契數(shù)

intfib(intn)

intresult;

intpre_result;

intnext_older_result;

result=pre_result=1;

while(n2)

n-=1;

next_older_result=pre_result;

pre_result=result;

result=pre_result+next_older_result;

returnresult;

}

總結(jié)：

1我們在用遞歸的時候是為了更好的解決問題，因?yàn)樗问礁忧逦?/p>

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

練習(xí)題

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

類容：

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

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

類容：

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

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

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

比如:

chararr[]="abcdef";

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

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

內(nèi)容：

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