2. 下列那一種資料結構最適合用來置放遞迴函式（recursive function）之區域變數（local variables）？
(A)hash table
(B)queue
(C)stack
(D)tree

【解題思路】

這題在考「遞迴」與「執行時記憶體配置」的基本概念。

關鍵字：

• 遞迴 recursive

• 區域變數 local variables

• 呼叫下一層時，需要記住上一層的狀態

只要是遞迴，就會一直「呼叫自己」，每一次呼叫都需要：

• 保存前一層的區域變數

• 保存返回位置（return address）

這些資料必須「後進先出（LIFO）」。
能做到 LIFO 的資料結構就是 堆疊（stack）。

因此，遞迴函式的區域變數一定是用 stack 承載。

【為什麼其他選項不正確（逐一破題）】

(A) hash table
用於快速查找 key-value，與遞迴呼叫的 LIFO 特性無關。

(B) queue
Queue 是「先進先出 FIFO」，與遞迴相反。

(C) stack
正確！遞迴一定用「呼叫堆疊 Call Stack」記住每層的資料。

(D) tree
遞迴常用在操作 tree 沒錯，但「區域變數」並不是存放在 tree，而是在程式的堆疊中。

【延伸知識】

遞迴函式呼叫時，程式會建立一個「堆疊框架 Stack Frame」：

裡面包含：

• 區域變數

• 參數

• return address（回去的位置）

• 暫存器狀態

這些全部都是放在「呼叫堆疊（Call Stack）」裡。

所以當遞迴越深，stack 會越來越大，也可能爆掉（stack overflow）。

【記憶技巧】

一句口訣：

遞迴層層疊，所以一定用堆疊。

或者：

遞迴＝呼叫堆疊 Call Stack。

【常見錯誤】

1. 看到遞迴與 tree 就誤選 tree
   遞迴常用來 traversal tree，但變數不是放在 tree 裡。

2. 誤認 queue
   Queue 是 FIFO，不符合遞迴必須「後呼叫先回來」的特性。

3. 忽略 stack overflow
   遞迴太深 stack 會爆，所以 stack 是遞迴的核心限制。