遞歸函數(shù)c語言用法 遞歸函數(shù)c語言例子

C語言遞歸算法？

本人學(xué)c++，c的語法已經(jīng)淡忘了，但是遞歸不管什么語言都是一個(gè)原理

公司主營業(yè)務(wù)：網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè)、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)推出通州免費(fèi)做網(wǎng)站回饋大家。

其實(shí)簡單一點(diǎn)來說就像數(shù)學(xué)里面的數(shù)列的通項(xiàng)公式：

例如一個(gè)數(shù)列是2，4，6，8，10......

很容易就可以得到通項(xiàng)公式是a[n]=2*n n是大于0的整數(shù)

你肯定學(xué)過這個(gè)數(shù)列的另外一種表示方式就是： a[1]=2, a[n]=a[n-1]+2 n是大于1的整數(shù)

其實(shí)這就是一個(gè)遞歸的形式，只要你知道初始項(xiàng)的值，未知項(xiàng)和前幾項(xiàng)之間的關(guān)系就可以知道整個(gè)數(shù)列。

程序例子：比如你要得到第x項(xiàng)的值

普通循環(huán)：

for(int i=1; i=n; i++)

if (i == x)

cout 2*i; /*cout 相當(dāng)于 c里面的printf,就是輸出.*/

遞歸：

int a(int x) {

if (x = 1)

return 2; /* 第一項(xiàng)那肯定是2了，這個(gè)也是遞歸的終止條件！ */

else return a(x-1)+2; /* 函數(shù)自身調(diào)用自身是遞歸的一個(gè)特色 */

比如x=4,那么用數(shù)學(xué)表示就是a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2

其實(shí)遞歸方法最接近自然，也是最好思考的一個(gè)方法，難點(diǎn)就是把對象建模成遞歸形式，但是好多問題本身就是以遞歸形式出現(xiàn)的。

普通遞歸就是數(shù)據(jù)結(jié)構(gòu)上的堆棧，先進(jìn)后出。

例如上面x=4,把a(bǔ)(4)放入棧底，然后放入a(3),然后a(2),a(1),a(1)的值已知，出棧，a(1)=2,a(2)出棧a(2)=a(1)+2=2+2=4,a(3)出棧a(3)=a(2)+2=(a(1)+2)+2=6,a(4)出棧a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2=8

再比如樓上的階乘例子，當(dāng)n=0 或 1時(shí),0!=1,1!=1,這個(gè)是階乘的初始值，也是遞歸的終止條件。然后我們知道n!=n*(n-1)!,當(dāng)n1時(shí),這樣我們又有了遞歸形式，又可以以遞歸算法設(shè)計(jì)程序了。（樓上已給出譚老的程序，我就不寫了）。

我給出一種優(yōu)化的遞歸算法---尾遞歸。

從我給出的第一算法可以看出，先進(jìn)棧再出棧，遞歸的效率是很低的。速度上完全比不上迭代（循環(huán)）。但是尾遞歸引入了一個(gè)新的函數(shù)參數(shù)，用這個(gè)新的函數(shù)參數(shù)來記錄中間值.

普通遞歸階乘fac(x),就1個(gè)x而已，尾遞歸用2個(gè)參數(shù)fac(x,y),y存放階乘值。

所以譚老的程序就變成

// zysable's tail recursive algorithm of factorial.

int fac(int x, int y) {

if (x == 1)

return y;

else return fac(x-1, y*x);}

int ff(int x) {

if (x == 0)

return 1;

else return fac(x,1);}

對于這個(gè)程序我們先看函數(shù)ff，函數(shù)ff其實(shí)是對fac的一個(gè)封裝函數(shù)，純粹是為了輸入方便設(shè)計(jì)的，通過調(diào)用ff(x)來調(diào)用fac(x,1),這里常數(shù)1就是當(dāng)x=1的時(shí)候階乘值了，我通過走一遍當(dāng)x=3時(shí)的值即為3!來說明一下。

首先ff(3),x!=0,執(zhí)行fac(3,1).第一次調(diào)用fac，x=3,y=1,x!=1,調(diào)用fac(x-1,y*x),新的x=2,y=3*1=3,這里可以看到，y已經(jīng)累計(jì)了一次階乘值了，然后x還是!=1,繼續(xù)第三次調(diào)用fac(x-1,y*x),新的x=1,y=2*3=6,然后x=1了，返回y的值是6，也就是3！.你會發(fā)現(xiàn)這個(gè)遞歸更類似于迭代了。事實(shí)上我們用了y記錄了普通遞歸時(shí)候，出棧的乘積，所以減少了出棧后的步驟，而且現(xiàn)在世界上很多程序員都在倡議用尾遞歸取消循環(huán)，因?yàn)橛行┰诤芏嘟忉屍魃衔策f歸比迭代稍微效率一點(diǎn).

基本所有普通遞歸的問題都可以用尾遞歸來解決。

一個(gè)問題以遞歸來解決重要的是你能抽象出問題的遞歸公式，只要遞歸公式有了，你就可以放心大膽的在程序中使用，另外一個(gè)重點(diǎn)就是遞歸的終止條件；

其實(shí)這個(gè)終止條件也是包含在遞歸公式里面的，就是初始值的定義。英文叫define initial value. 用普通遞歸的時(shí)候不要刻意讓自己去人工追蹤程序，查看運(yùn)行過程，有些時(shí)候你會發(fā)現(xiàn)你越看越不明白，只要遞歸公式轉(zhuǎn)化成程序語言正確了，結(jié)果必然是正確的。學(xué)遞歸的初學(xué)者總是想用追蹤程序運(yùn)行來讓自己來了解遞歸，結(jié)果越弄越糊涂。

如果想很清楚的了解遞歸，有種計(jì)算機(jī)語言叫scheme,完全遞歸的語言，因?yàn)闆]有循環(huán)語句和賦值語句。但是國內(nèi)人知道的很少，大部分知道是的lisp。

好了，就給你說到這里了，希望你能學(xué)好遞歸。

PS:遞歸不要濫用，否則程序極其無效率，要用也用尾遞歸。by 一名在美國的中國程序員zysable。

c語言怎么用遞歸調(diào)用函數(shù)的方法求n的階乘？

1、打開VC6.0軟件，新建一個(gè)C語言的項(xiàng)目：

2、接下來編寫主程序，首先定義用來求階乘的遞歸函數(shù)以及主函數(shù)。在main函數(shù)里定義變量sum求和，調(diào)用遞歸函數(shù)fact()，并將返回值賦予sum，最后使用printf打印sum的結(jié)果，主程序就編寫完了：

3、最后運(yùn)行程序，觀察輸出的結(jié)果。以上就是C語言使用遞歸求階乘的寫法：

c語言遞歸函數(shù)

遞歸（recursion）就是子程序（或函數(shù)）直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自己，是一種描述問題和解決問題的基本方法。

遞歸通常用來解決結(jié)構(gòu)自相似的問題。所謂結(jié)構(gòu)自相似，是指構(gòu)成原問題的子問題與原問題在結(jié)構(gòu)上相似，可以用類似的方法解決。具體地，整個(gè)問題的解決，可以分為兩部分：第一部分是一些特殊情況，有直接的解法；第二部分與原問題相似，但比原問題的規(guī)模小。實(shí)際上，遞歸是把一個(gè)不能或不好解決的大問題轉(zhuǎn)化為一個(gè)或幾個(gè)小問題，再把這些小問題進(jìn)一步分解成更小的問題，直至每個(gè)小問題都可以直接解決。因此，遞歸有兩個(gè)基本要素：

（1）邊界條件：確定遞歸到何時(shí)終止，也稱為遞歸出口。

（2）遞歸模式：大問題是如何分解為小問題的，也稱為遞歸體。遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果

漢諾塔問題：對漢諾塔問題的求解，可以通過以下3個(gè)步驟實(shí)現(xiàn)：

（1）將塔上的n-1個(gè)碟子借助塔C先移到塔B上；

（2）把塔A上剩下的一個(gè)碟子移到塔C上；

（3）將n-1個(gè)碟子從塔B借助塔A移到塔C上。

在遞歸函數(shù)中，調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)，需要注意的是遞歸函數(shù)的調(diào)用層次，如果把調(diào)用遞歸函數(shù)的主函數(shù)稱為第0層，進(jìn)入函數(shù)后，首次遞歸調(diào)用自身稱為第1層調(diào)用；從第i層遞歸調(diào)用自身稱為第i+1層。反之，退出第i+1層調(diào)用應(yīng)該返回第i層。采用圖示方法描述遞歸函數(shù)的運(yùn)行軌跡，從中可較直觀地了解到各調(diào)用層次及其執(zhí)行情況，具體方法如下：

（1）寫出函數(shù)當(dāng)前調(diào)用層執(zhí)行的各語句，并用有向弧表示語句的執(zhí)行次序；

（2）對函數(shù)的每個(gè)遞歸調(diào)用，寫出對應(yīng)的函數(shù)調(diào)用，從調(diào)用處畫一條有向弧指向被調(diào)用函數(shù)入口，表示調(diào)用路線，從被調(diào)用函數(shù)末尾處畫一條有向弧指向調(diào)用語句的下面，表示返回路線；

（3）在返回路線上標(biāo)出本層調(diào)用所得的函數(shù)值。n=3時(shí)漢諾塔算法的運(yùn)行軌跡如下圖所示，有向弧上的數(shù)字表示遞歸調(diào)用和返回的執(zhí)行順序

三、遞歸函數(shù)的內(nèi)部執(zhí)行過程

一個(gè)遞歸函數(shù)的調(diào)用過程類似于多個(gè)函數(shù)的嵌套的調(diào)用，只不過調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)。為了保證遞歸函數(shù)的正確執(zhí)行，系統(tǒng)需設(shè)立一個(gè)工作棧。具體地說，遞歸調(diào)用的內(nèi)部執(zhí)行過程如下：

（1）運(yùn)動開始時(shí)，首先為遞歸調(diào)用建立一個(gè)工作棧，其結(jié)構(gòu)包括值參、局部變量和返回地址；

（2）每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧；

（3）每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。

上述漢諾塔算法執(zhí)行過程中，工作棧的變化如下圖所示，其中棧元素的結(jié)構(gòu)為（返回地址，n值，A值，B值，C值），返回地址對應(yīng)算法中語句的行號，分圖的序號對應(yīng)圖中遞歸調(diào)用和返回的序號

我可以幫助你，你先設(shè)置我最佳答案后，我百度Hii教你。

c語言函數(shù)遞歸調(diào)用

我給你舉個(gè)簡單的例子你就明白了，你可以假設(shè)n=3

然后代入這個(gè)函數(shù)，a(3)=a(2)+5;而a(2)=a(1)+5;a(1)=1

所以最后就是a(3)=1+5+5=11…

同理你可以算出a(10)=1+5*9=46

滿意請采納

網(wǎng)站名稱：遞歸函數(shù)c語言用法 遞歸函數(shù)c語言例子
鏈接URL：http://muchs.cn/article46/doshjhg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、微信小程序、網(wǎng)站收錄、域名注冊、電子商務(wù)、服務(wù)器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)