高考申論題
115年
[資訊處理] 資料結構
第 鿩 題
📖 題組：
考慮以下兩個互相呼叫（mutually recursive）的 C 語言函式： ```c int foo(int n) { if (n <= 1) return 1; return foo(n - 1) + bar(n - 1) + 2; } int bar(int n) { if (n <= 1) return 1; return foo(n - 1) + bar(n - 1); } ``` 請回答下列問題：（每一小題請寫出推導過程，無推導過程不予計分。）
考慮以下兩個互相呼叫（mutually recursive）的 C 語言函式： ```c int foo(int n) { if (n <= 1) return 1; return foo(n - 1) + bar(n - 1) + 2; } int bar(int n) { if (n <= 1) return 1; return foo(n - 1) + bar(n - 1); } ``` 請回答下列問題：（每一小題請寫出推導過程，無推導過程不予計分。）
當執行 foo(10)時，一共會呼叫 foo()函式幾次（包含最外層 foo(10)的這一次呼叫）？（10 分）
📝 此題為申論題
思路引導 VIP
利用遞迴關係式推導函式呼叫次數。 設 $F(n)$ 為呼叫 foo(n) 產生的 foo() 總呼叫次數。$B(n)$ 為呼叫 bar(n) 產生的 foo() 總呼叫次數。
🤖
AI 詳解
AI 專屬家教
【考點分析】 遞迴函式（互相呼叫）的執行次數分析與遞迴關係式（Recurrence Relation）求解。 【理論/法規依據】
▼ 還有更多解析內容