考慮以下兩個互相呼叫（mutually recursive）的C 語言函式： int foo(int n) { if (n <= 1) return 1; re…

題目

考慮以下兩個互相呼叫（mutually recursive）的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 分） 執行foo(10)的最終回傳結果為何？（10 分） 以Big-O 表示foo(n)的時間複雜度（time complexity）。本題若同一個 「函式與參數」組合被呼叫多次，每次都重新計算，不會儲存先前的 計算結果供之後使用。（5 分）

參考解答（AI 生成，非官方）

• 一、定義與基礎值：令F(n)、B(n)分別為foo(n)、bar(n)的回傳值。n≤1時F(n)=B(n)=1；因此F(1)=1、B(1)=1、F(2)=1+1+2=4、B(2)=1+1=2。此為後續推導的初始條件。
• 二、推導通式：n≥3時，B(n)=F(n-1)+B(n-1)，且F(n)=F(n-1)+B(n-1)+2=B(n)+2，故B(n)=F(n)-2。代回F(n)=F(n-1)+(F(n-1)-2)+2=2F(n-1)。由F(2)=4得F(n)=2^n（n≥2），所以F(10)=2^10=1024。
• 三、foo呼叫次數：令f(n)、b(n)分別為執行foo(n)、bar(n)時所呼叫foo的次數（含自身）。f(1)=1、b(1)=0；n≥2時f(n)=1+f(n-1)+b(n-1)，b(n)=f(n-1)+b(n-1)。兩式相減得f(n)=b(n)+1，再代入得b(n)=2b(n-1)+1，故b(n)=2^(n-1)-1、f(n)=2^(n-1)。因此f(10)=2^9=512次。
• 四、時間複雜度：在無記憶化（no memoization）下，每個foo或bar呼叫都會再產生兩個同階的子呼叫，遞迴式為T(n)=2T(n-1)+O(1)，展開得T(n)=O(2^n)，且為Θ(2^n)。本題實際呼叫次數呈指數成長，並非O(n)或O(n^2)；遞迴深度為O(n)，額外空間主要為呼叫堆疊O(n)。

AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。

官方資料

• 官方試題 PDF