資料結構與演算法
函數 f(x, y) 定義為「若 y 為0則回傳 x，否則回傳 f(y, x mod y)」。呼叫 f(84, 36) 時的回傳值，以及 f 被呼叫的次數（含第一次呼叫）的組合為下列何者？
- A回傳值12，呼叫3次
- B回傳值12，呼叫4次
- C回傳值6，呼叫3次
查看答案與解析
正確答案：A. 回傳值12，呼叫3次
f(84, 36) 因 84 mod 36 = 12 而呼叫 f(36, 12)，又因 36 mod 12 = 0 而呼叫 f(12, 0)，由於 y 為0，回傳12。呼叫為 f(84, 36)、f(36, 12)、f(12, 0) 共3次，這就是以輾轉相除法（歐幾里得演算法）求最大公因數的計算。此函數直接回傳遞迴呼叫結果，屬於尾端遞迴，若編譯器進行尾端呼叫最佳化就能轉換成迴圈，即使呼叫很深也不會持續消耗堆疊。
- A. 正確。f(84, 36)→f(36, 12)→f(12, 0) 共3次，回傳84與36的最大公因數12。
- B. 在 f(12, 0) 時 y 為0就結束，因此沒有第4次呼叫。
- C. 84與36的最大公因數是12（84 = 12×7、36 = 12×3）。