司法三等申論題
113年
[檢察事務官電子資訊組] 程式語言
第 一 題
📖 題組：
二、遞迴函式（Recursion）是程式語言常用的解題技巧之一，請回答下列問題：
二、遞迴函式（Recursion）是程式語言常用的解題技巧之一，請回答下列問題：
📝 此題為申論題，共 4 小題
小題 (一)
請說明何謂程式語言的遞迴函式，撰寫遞迴函式需要那些條件？（10 分）
思路引導 VIP
看到「遞迴」題型，首先應精確答出「函式呼叫自身」的定義，接著務必點出遞迴的兩大核心要件：「終止條件（Base case）」與「遞迴步驟（Recursive step）」。為了爭取高分，建議補充遞迴在記憶體中「呼叫堆疊（Call Stack）」的運作機制與優缺點。
小題 (二)
請用迴圈（Iteration）以及遞迴分別撰寫計算第 n 個費式數列的值。費氏數列由 0 和 1 開始，之後費氏數列的值就是由之前的兩數相加而得出。程式語言可使用 C/C++、Python 或是 Java 撰寫。（10 分）
思路引導 VIP
看到此題，首先應在腦海中浮現費氏數列的數學遞迴關係式：F(n) = F(n-1) + F(n-2)。接著，需意識到遞迴解法是直接翻譯數學定義（需留意終止條件），而迴圈解法則是利用變數進行狀態的滾動更新（需維護前兩項的值）。作答時，除了寫出程式碼，加上變數生命週期與記憶體配置（Stack Frame）的分析能大幅提升分數。
小題 (三)
請說明為何用遞迴函式撰寫第 n 個費式數列的值，其執行的時間會比用迴圈來得多。（15 分）
思路引導 VIP
看到此題，應先點出演算法層面的致命傷：遞迴展開時會產生「重疊子問題」導致指數級 O(2^n) 的重複計算。接著從編譯器與記憶體管理角度，切入「函數呼叫開銷（Stack Frame 配置與釋放）」對執行時間與空間的影響，最後輔以 C/Java 程式碼標註生命週期，展示遞迴與迴圈的時間/空間複雜度差異。
小題 (四)
請修改上述的費式數列遞迴函式版本，使其可以加快執行的時間（接近迴圈的版本）。（15 分）
思路引導 VIP
看到費氏數列的遞迴優化，應立刻聯想到「重疊子問題」導致的指數級時間複雜度 O(2^n)。解法的核心是消除重複計算，最佳策略為改寫成「尾遞迴（Tail Recursion）」，透過參數傳遞迴圈狀態，使其時間複雜度降為 O(n)，且在編譯器最佳化下空間複雜度可達 O(1)，完美模擬迴圈在記憶體中的行為。