首頁猿問編譯語言都是要求先定義后調(diào)用的，但...

編譯語言都是要求先定義后調(diào)用的，但是fib函數(shù)沒有完成定義就可以使用了嗎？

嵌入式 C

阿晨1998 2022-10-02 13:09:56

int fib(int n) { if(0 == n) return 0; if(1 == n) return 1; if(n > 1) return fib(n-1)+fib(n-2);//這此刻函數(shù)fib還沒有完成定義，怎么可以調(diào)用呢？ } 調(diào)用的時候fib雖然是一個指針，但是編譯器是怎么展開的？運行時展開，還是編譯時候形成指令？調(diào)用到return fib(n-1)+fib(n-2)的時候，確實fib已經(jīng)存在，但是fib沒有定義完全呢？

查看完整描述

2 回答

慕哥9229398

TA貢獻1877條經(jīng)驗獲得超6個贊

幾乎每一本c
語言基礎(chǔ)的書都講到了函數(shù)遞歸的問題，但是初學(xué)者仍然容易在這個地方犯錯誤。先看看下面的例子：
void
fun(int
i)
{
if
(i>0)
{
fun(i/2);
}
printf("%d\n",i);
}
intmain()
{
fun(10);
return
0;
}
問：輸出結(jié)果是什么？
這是我上課時，一個學(xué)生問我的問題。他不明白為什么輸出的結(jié)果會是這樣：
0
1
2
5
10
他認為應(yīng)該輸出0。因為當i
小于或等于0
時遞歸調(diào)用結(jié)束，然后執(zhí)行printf
函數(shù)打印i
的值。
這就是典型的沒明白什么是遞歸。其實很簡單，printf("%d\n",i);語句是fun
函數(shù)的一部分，肯定執(zhí)行一次fun
函數(shù)，就要打印一行。怎么可能只打印一次呢？關(guān)鍵就是不明白怎么展開遞歸函數(shù)。展開過程如下：
void
fun(int
i)
{
if
(i>0)
{
//fun(i/2);
if(i/2>0)
{
if(i/4>0)
{
…
}
printf("%d\n",i/4);
}
printf("%d\n",i/2);
}
printf("%d\n",i);
}
這樣一展開，是不是清晰多了？其實遞歸本身并沒有什么難處，關(guān)鍵是其展開過程別弄錯了。
二、不使用任何變量編寫strlen
函數(shù)
看到這里，也許有人會說，strlen
函數(shù)這么簡單，有什么好討論的。是的，我相信你能熟練應(yīng)用這個函數(shù)，也相信你能輕易的寫出這個函數(shù)。但是如果我把要求提高一些呢：
不允許調(diào)用庫函數(shù)，也不允許使用任何全局或局部變量編寫intmy_strlen
(char
*strdest);似乎問題就沒有那么簡單了吧？這個問題曾經(jīng)在網(wǎng)絡(luò)上討論的比較熱烈，我?guī)缀跏侨獭坝^戰(zhàn)”，差點也忍不住手癢了。不過因為我的解決辦法在我看到帖子時已經(jīng)有人提出了，所以作罷。
解決這個問題的辦法由好幾種，比如嵌套有編語言。因為嵌套匯編一般只在嵌入式底層開發(fā)中用到，所以本書就不打算討論c
語言嵌套匯編的知識了。有興趣的讀者，可以查找相關(guān)資料。
也許有的讀者想到了用遞歸函數(shù)來解決這個問題。是的，你應(yīng)該想得到，因為我把這個問題放在講解函數(shù)遞歸的時候討論。既然已經(jīng)有了思路，這個問題就很簡單了。代碼如下：
intmy_strlen(
const
char*
strdest
)
{
assert(null
!=
strdest);
if
('\0'
==
*strdest)
{
return
0;
}
else
{
return
(1
+
my_strlen(++strdest));
}
}
第一步：用assert
宏做入口校驗。
第二步：確定參數(shù)傳遞過來的地址上的內(nèi)存存儲的是否為'\0'。如果是，表明這是一個空字符串，或者是字符串的結(jié)束標志。
第三步：如果參數(shù)傳遞過來的地址上的內(nèi)存不為'\0'，則說明這個地址上的內(nèi)存上存儲的是一個字符。既然這個地址上存儲了一個字符，那就計數(shù)為1，然后將地址加1
個char類型元素的大小，然后再調(diào)用函數(shù)本身。如此循環(huán)，當?shù)刂芳拥阶址慕Y(jié)束標志符'\0'時，遞歸停止。
當然，同樣是利用遞歸，還有人寫出了更加簡潔的代碼：
intmy_strlen(
const
char*
strdest
)
{
return
*strdest?1+strlen(strdest+1):0;
}
這里很巧妙的利用了問號表達式，但是沒有做參數(shù)入口校驗，同時用*strdest
來代替('\0'==
*strdest)也不是很好。所以，這種寫法雖然很簡潔，但不符合我們前面所講的編碼規(guī)范?？梢愿膶懸幌拢?br/>intmy_strlen(
const
char*
strdest
)
{
assert(null
!=
strdest);
return
('\0'
!=
*strdest)?(1+my_strlen(strdest+1)):0;
}
上面的問題利用函數(shù)遞歸的特性就輕易的搞定了，也就是說每調(diào)用一遍my_strlen
函數(shù)，其實只判斷了一個字節(jié)上的內(nèi)容。但是，如果傳入的字符串很長的話，就需要連續(xù)多次函數(shù)調(diào)用，而函數(shù)調(diào)用的開銷比循環(huán)來說要大得多，所以，遞歸的效率很低，遞歸的深度太大甚至可能出現(xiàn)錯誤（比如棧溢出）。所以，平時寫代碼，不到萬不得已，盡量不要用遞歸。即便是要用遞歸，也要注意遞歸的層次不要太深，防止出現(xiàn)棧溢出的錯誤；同時遞歸的停止條件一定要正確，否則，遞歸可能沒完沒了。