高考申論題
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); } ``` 請回答下列問題：（每一小題請寫出推導過程，無推導過程不予計分。）
以 Big-O 表示 foo(n)的時間複雜度（time complexity）。本題若同一個「函式與參數」組合被呼叫多次，每次都重新計算，不會儲存先前的計算結果供之後使用。（5 分）
📝 此題為申論題
思路引導 VIP
無記憶化(Memoization) 的遞迴，每個函式內都有 2 個分支 (foo 和 bar)。 總操作次數與總函式呼叫次數成正比。