C語言：遞歸函數(shù)的定義疑惑

幾乎每一本c

創(chuàng)新互聯(lián)建站長(zhǎng)期為成百上千客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為合作企業(yè)提供專業(yè)的成都做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)，合作網(wǎng)站改版等技術(shù)服務(wù)。擁有10余年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

語言基礎(chǔ)的書都講到了函數(shù)遞歸的問題，但是初學(xué)者仍然容易在這個(gè)地方犯錯(cuò)誤。先看看下面的例子：

void

fun(int

i)

{

if

(i0)

{

fun(i/2);

}

printf("%d\n",i);

}

intmain()

{

fun(10);

return

0;

}

問：輸出結(jié)果是什么？

這是我上課時(shí)，一個(gè)學(xué)生問我的問題。他不明白為什么輸出的結(jié)果會(huì)是這樣：

1

2

5

10

他認(rèn)為應(yīng)該輸出0。因?yàn)楫?dāng)i

小于或等于0

時(shí)遞歸調(diào)用結(jié)束，然后執(zhí)行printf

函數(shù)打印i

的值。

這就是典型的沒明白什么是遞歸。其實(shí)很簡(jiǎn)單，printf("%d\n",i);語句是fun

函數(shù)的一部分，肯定執(zhí)行一次fun

函數(shù)，就要打印一行。怎么可能只打印一次呢？關(guān)鍵就是不明白怎么展開遞歸函數(shù)。展開過程如下：

void

fun(int

i)

{

if

(i0)

{

//fun(i/2);

if(i/20)

{

if(i/40)

{

…

}

printf("%d\n",i/4);

}

printf("%d\n",i/2);

}

printf("%d\n",i);

}

這樣一展開，是不是清晰多了？其實(shí)遞歸本身并沒有什么難處，關(guān)鍵是其展開過程別弄錯(cuò)了。

二、不使用任何變量編寫strlen

函數(shù)

看到這里，也許有人會(huì)說，strlen

函數(shù)這么簡(jiǎn)單，有什么好討論的。是的，我相信你能熟練應(yīng)用這個(gè)函數(shù)，也相信你能輕易的寫出這個(gè)函數(shù)。但是如果我把要求提高一些呢：

不允許調(diào)用庫函數(shù)，也不允許使用任何全局或局部變量編寫intmy_strlen

(char

*strdest);似乎問題就沒有那么簡(jiǎn)單了吧？這個(gè)問題曾經(jīng)在網(wǎng)絡(luò)上討論的比較熱烈，我?guī)缀跏侨獭坝^戰(zhàn)”，差點(diǎn)也忍不住手癢了。不過因?yàn)槲业慕鉀Q辦法在我看到帖子時(shí)已經(jīng)有人提出了，所以作罷。

解決這個(gè)問題的辦法由好幾種，比如嵌套有編語言。因?yàn)榍短讌R編一般只在嵌入式底層開發(fā)中用到，所以本書就不打算討論c

語言嵌套匯編的知識(shí)了。有興趣的讀者，可以查找相關(guān)資料。

也許有的讀者想到了用遞歸函數(shù)來解決這個(gè)問題。是的，你應(yīng)該想得到，因?yàn)槲野堰@個(gè)問題放在講解函數(shù)遞歸的時(shí)候討論。既然已經(jīng)有了思路，這個(gè)問題就很簡(jiǎn)單了。代碼如下：

intmy_strlen(

const

char*

strdest

)

{

assert(null

!=

strdest);

if

('\0'

==

*strdest)

{

return

0;

}

else

{

return

(1

+

my_strlen(++strdest));

}

}

第一步：用assert

宏做入口校驗(yàn)。

第二步：確定參數(shù)傳遞過來的地址上的內(nèi)存存儲(chǔ)的是否為'\0'。如果是，表明這是一個(gè)空字符串，或者是字符串的結(jié)束標(biāo)志。

第三步：如果參數(shù)傳遞過來的地址上的內(nèi)存不為'\0'，則說明這個(gè)地址上的內(nèi)存上存儲(chǔ)的是一個(gè)字符。既然這個(gè)地址上存儲(chǔ)了一個(gè)字符，那就計(jì)數(shù)為1，然后將地址加1

個(gè)char類型元素的大小，然后再調(diào)用函數(shù)本身。如此循環(huán)，當(dāng)?shù)刂芳拥阶址慕Y(jié)束標(biāo)志符'\0'時(shí)，遞歸停止。

當(dāng)然，同樣是利用遞歸，還有人寫出了更加簡(jiǎn)潔的代碼：

intmy_strlen(

const

char*

strdest

)

{

return

*strdest?1+strlen(strdest+1):0;

}

這里很巧妙的利用了問號(hào)表達(dá)式，但是沒有做參數(shù)入口校驗(yàn)，同時(shí)用*strdest

來代替('\0'==

*strdest)也不是很好。所以，這種寫法雖然很簡(jiǎn)潔，但不符合我們前面所講的編碼規(guī)范。可以改寫一下：

intmy_strlen(

const

char*

strdest

)

{

assert(null

!=

strdest);

return

('\0'

!=

*strdest)?(1+my_strlen(strdest+1)):0;

}

上面的問題利用函數(shù)遞歸的特性就輕易的搞定了，也就是說每調(diào)用一遍my_strlen

函數(shù)，其實(shí)只判斷了一個(gè)字節(jié)上的內(nèi)容。但是，如果傳入的字符串很長(zhǎng)的話，就需要連續(xù)多次函數(shù)調(diào)用，而函數(shù)調(diào)用的開銷比循環(huán)來說要大得多，所以，遞歸的效率很低，遞歸的深度太大甚至可能出現(xiàn)錯(cuò)誤（比如棧溢出）。所以，平時(shí)寫代碼，不到萬不得已，盡量不要用遞歸。即便是要用遞歸，也要注意遞歸的層次不要太深，防止出現(xiàn)棧溢出的錯(cuò)誤；同時(shí)遞歸的停止條件一定要正確，否則，遞歸可能沒完沒了。

講一下c語言中遞歸函數(shù)的使用方法

遞歸函數(shù)有三點(diǎn)要求：

1，遞歸的終止點(diǎn)，即遞歸函數(shù)的出口

2，不斷的遞歸調(diào)用自身

3，遞歸函數(shù)主體內(nèi)容，即遞歸函數(shù)需要做的事情

ps：3一般可以放在2的前面或者后面，一般1放最前面。另外，2和3可以根據(jù)不同的需要合并，比如，有時(shí)候遞歸函數(shù)的主體就是返回調(diào)用下層函數(shù)所得到的結(jié)果。

具體例子如下：

void?fun(int?n)

{

if(n=0)?return;???//1?這是遞歸的終點(diǎn)，即出口

fun(n-1);????????//2、遞歸函數(shù)自身的調(diào)用

coutnendl;?????//3?遞歸函數(shù)的主體內(nèi)容

}

2,3合并的情況

int?fun(int?n)

{

if(n=0)?return?0;

return?fun(n-1)+fun(n-2);??//2?3合并

}

c語言怎么用遞歸函數(shù)

首先是要這個(gè)求解的問題，適合用遞歸方法來進(jìn)行求解。找到這個(gè)遞歸解法結(jié)束遞歸的條件。遞歸函數(shù)中，首先第一個(gè)語句就是如果滿足遞歸條件，就直接返回確定的值，否則返回使用遞歸方法求解的表達(dá)式。