身心障礙人員考試身障四等-資訊處理類科計算機概要105 年第 40 題單選題
下列 C 程式從開始執行到結束,共呼叫幾次 foo 函式(function)?
int foo(int a)
{
if ((a==0) || (a==1)) return 1;
else return (foo(a-1) + foo(a-2));
}
int main(void)
{
printf("%d\n", foo(5));
}
D正確答案
費氏數列遞迴呼叫次數題,foo(5) 總呼叫數為 15 次。
為什麼答案是 D
展開遞迴樹:T(5)=T(4)+T(3)+1=9+5+1=15,正確。
載入中…
完整詳解
Pro · 無限重點 費氏數列遞迴呼叫次數題,foo(5) 總呼叫數為 15 次。
遞迴呼叫次數 T(n)=T(n-1)+T(n-2)+1,T(0)=T(1)=1。T(5)=15。
逐選項分析
A✕
1 僅是 foo(0) 或 foo(1) 的呼叫次數,非 foo(5) 的總數。
B✕ 陷阱
7 是 foo(4) 的呼叫次數,誤算少一層遞迴會得此答案。
C✕ 陷阱
8 是 foo(5) 的回傳值(費氏數),不是呼叫次數,容易混淆。
D✓ 正確
展開遞迴樹:T(5)=T(4)+T(3)+1=9+5+1=15,正確。
foo(n) 呼叫次數 T(n) 與回傳值 F(n)
| n | T(n) 呼叫次數 | F(n) 回傳值 | 公式 |
|---|
| 0 | 1 | 1 | 基底 |
| 1 | 1 | 1 | 基底 |
| 2 | 3 | 2 | T(1)+T(0)+1 |
| 3 | 5 | 3 | T(2)+T(1)+1 |
| 4 | 9 | 5 | T(3)+T(2)+1 |
| 5 | 15 | 8 | T(4)+T(3)+1 |