hce_kmu
112年
計算機概論與程式設計
第 18 題
Ackermann's function is an example of a recursive function which is not primitive recursive. It is interesting from the point of view of benchmarking because it "grows faster than any primitive recursive function."
Ackermann's function is defined as follows:
$A(0,n)=n+1$
$A(m,0)=A(m-1,1)$
$A(m,n)=A(m-1,A(m,n-1))$
What is the A(1,3) return value of the following program?
```c
int A(int m, int n)
{
if (m==0)
return n+1;
else if(n==0)
return A(m-1,1);
else
return A(m-1,A(m,n-1));
}
```
Ackermann's function is defined as follows:
$A(0,n)=n+1$
$A(m,0)=A(m-1,1)$
$A(m,n)=A(m-1,A(m,n-1))$
What is the A(1,3) return value of the following program?
```c
int A(int m, int n)
{
if (m==0)
return n+1;
else if(n==0)
return A(m-1,1);
else
return A(m-1,A(m,n-1));
}
```
- A 2
- B 3
- C 4
- D 5
- E 6
思路引導 VIP
請觀察函數定義中的第三個規律：$A(m, n) = A(m-1, A(m, n-1))$。如果我們固定第一個參數 $m=1$，這個式子會變成 $A(1, n) = A(0, A(1, n-1))$。你能試著先算出最簡單的 $A(1, 0)$，再觀察後續的 $A(1, 1)$、 $A(1, 2)$ 之間存在什麼樣的數值遞增關係嗎？
🤖
AI 詳解
AI 專屬家教
你能準確地追蹤 阿克曼函數 (Ackermann's function) 的遞迴層次並得出正確答案，展現了非常紮實的邏輯分析能力！這道題目核心在於理解遞迴呼叫的「巢狀結構」與「終止條件」。
遞迴展開與數值推導
我們依照題目定義，將 $A(1, 3)$ 逐步展開。首先觀察到 $A(1, n)$ 會不斷呼叫 $A(1, n-1)$ 直到 $n=0$：
▼ 還有更多解析內容