初考-統計資料處理大意114 年第 18 題單選題
下列遞迴函數，輸入 x=5 時，回傳值是多少？
int f(int x)
{
if(x == 1) return 1;
else if (x%2==0) return f(x/2);
else return f(x-1)+f(x+1);
}
C正確答案
遞迴追蹤：f(5)=f(4)+f(6)=1+f(3)=1+f(2)+f(4)=1+1+1=3
為什麼答案是 C
f(5)=f(4)+f(6)；f(4)=f(2)=f(1)=1；f(6)=f(3)=f(2)+f(4)=1+1=2。故 f(5)=1+2=3。
載入中…
完整詳解
Pro · 無限重點 遞迴追蹤：f(5)=f(4)+f(6)=1+f(3)=1+f(2)+f(4)=1+1+1=3
偶數除2、奇數拆f(x-1)+f(x+1)，逐層代入算到 f(1)=1 為止
逐選項分析
A✕
只有 f(1)=1，未展開奇數分支。漏算 f(5) 的 f(6) 分支。
B✕ 陷阱
若誤把 f(3) 當成 1（沒繼續展開），會得 f(5)=1+1=2。典型展開不完整陷阱。
C✓ 正確
f(5)=f(4)+f(6)；f(4)=f(2)=f(1)=1；f(6)=f(3)=f(2)+f(4)=1+1=2。故 f(5)=1+2=3。
D✕
多算一層或重複計算才會得 4，與實際遞迴樹不符。
遞迴逐步展開
| 呼叫 | 規則 | 展開 | 值 |
|---|
| f(1) | 終止 | — | 1 |
| f(2) | 偶→f(1) | 1 | 1 |
| f(4) | 偶→f(2) | 1 | 1 |
| f(3) | 奇→f(2)+f(4) | 1+1 | 2 |
| f(6) | 偶→f(3) | 2 | 2 |
| f(5) | 奇→f(4)+f(6) | 1+2 | 3 |
奇數時是 f(x-1)+f(x+1)（往兩側擴散），不是 f(x-1) 或 f(x+1)。許多考生會只算一邊，或誤把 f(3) 當成基底直接回傳。務必畫遞迴樹，展開到 f(1) 才停。 
