int fib(int n) { if(0 == n) return 0; if(1 == n) return 1; if(n > 1) return fib(n-1)+fib(n-2);//這此刻函數fib還沒有完成定義，怎么可以調用呢？ } 調用的時候fib雖然是一個指針，但是編譯器是怎么展開的？運行時展開，還是編譯時候形成指令？ 調用到return fib(n-1)+fib(n-2)的時候，確實fib已經存在，但是fib沒有定義完全呢？
2 回答
慕哥9229398
TA貢獻1877條經驗 獲得超6個贊
幾乎每一本c
語言基礎的書都講到了函數遞歸的問題，但是初學者仍然容易在這個地方犯錯誤。先看看下面的例子：
void
fun(int
i)
{
if
(i>0)
{
fun(i/2);
}
printf("%d\n",i);
}
intmain()
{
fun(10);
return
0;
}
問：輸出結果是什么？
這是我上課時，一個學生問我的問題。他不明白為什么輸出的結果會是這樣：
0
1
2
5
10
他認為應該輸出0。因為當i
小于或等于0
時遞歸調用結束，然后執行printf
函數打印i
的值。
這就是典型的沒明白什么是遞歸。其實很簡單，printf("%d\n",i);語句是fun
函數的一部分，肯定執行一次fun
函數，就要打印一行。怎么可能只打印一次呢？關鍵就是不明白怎么展開遞歸函數。展開過程如下：
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);
}
這樣一展開，是不是清晰多了？其實遞歸本身并沒有什么難處，關鍵是其展開過程別弄錯了。
二、不使用任何變量編寫strlen
函數
看到這里，也許有人會說，strlen
函數這么簡單，有什么好討論的。是的，我相信你能熟練應用這個函數，也相信你能輕易的寫出這個函數。但是如果我把要求提高一些呢：
不允許調用庫函數，也不允許使用任何全局或局部變量編寫intmy_strlen
(char
*strdest);似乎問題就沒有那么簡單了吧？這個問題曾經在網絡上討論的比較熱烈，我幾乎是全程“觀戰”，差點也忍不住手癢了。不過因為我的解決辦法在我看到帖子時已經有人提出了，所以作罷。
解決這個問題的辦法由好幾種，比如嵌套有編語言。因為嵌套匯編一般只在嵌入式底層開發中用到，所以本書就不打算討論c
語言嵌套匯編的知識了。有興趣的讀者，可以查找相關資料。
也許有的讀者想到了用遞歸函數來解決這個問題。是的，你應該想得到，因為我把這個問題放在講解函數遞歸的時候討論。既然已經有了思路，這個問題就很簡單了。代碼如下：
intmy_strlen(
const
char*
strdest
)
{
assert(null
!=
strdest);
if
('\0'
==
*strdest)
{
return
0;
}
else
{
return
(1
+
my_strlen(++strdest));
}
}
第一步：用assert
宏做入口校驗。
第二步：確定參數傳遞過來的地址上的內存存儲的是否為'\0'。如果是，表明這是一個空字符串，或者是字符串的結束標志。
第三步：如果參數傳遞過來的地址上的內存不為'\0'，則說明這個地址上的內存上存儲的是一個字符。既然這個地址上存儲了一個字符，那就計數為1，然后將地址加1
個char類型元素的大小，然后再調用函數本身。如此循環，當地址加到字符串的結束標志符'\0'時，遞歸停止。
當然，同樣是利用遞歸，還有人寫出了更加簡潔的代碼：
intmy_strlen(
const
char*
strdest
)
{
return
*strdest?1+strlen(strdest+1):0;
}
這里很巧妙的利用了問號表達式，但是沒有做參數入口校驗，同時用*strdest
來代替('\0'==
*strdest)也不是很好。所以，這種寫法雖然很簡潔，但不符合我們前面所講的編碼規范。可以改寫一下：
intmy_strlen(
const
char*
strdest
)
{
assert(null
!=
strdest);
return
('\0'
!=
*strdest)?(1+my_strlen(strdest+1)):0;
}
上面的問題利用函數遞歸的特性就輕易的搞定了，也就是說每調用一遍my_strlen
函數，其實只判斷了一個字節上的內容。但是，如果傳入的字符串很長的話，就需要連續多次函數調用，而函數調用的開銷比循環來說要大得多，所以，遞歸的效率很低，遞歸的深度太大甚至可能出現錯誤（比如棧溢出）。所以，平時寫代碼，不到萬不得已，盡量不要用遞歸。即便是要用遞歸，也要注意遞歸的層次不要太深，防止出現棧溢出的錯誤；同時遞歸的停止條件一定要正確，否則，遞歸可能沒完沒了。
慕哥6287543
TA貢獻1831條經驗 獲得超10個贊
函數只是一個標號地址，整個代碼在編譯連接后形成一段代碼段，被運行時放入代碼段中，整個代碼段地址也就確定，當調用時此函數時會把當前.pc入棧，參數通常采用棧傳遞過去，然后跳到函數入口執行，以后發生的一切都尊守這規律
- 2 回答
- 0 關注
- 141 瀏覽
添加回答
舉報
0/150
提交
取消