再帰関数 (アッカーマン関数) の値
出典: 平成30年度 春期 応用情報技術者試験 午前 問5 (IPA)
非負の整数 m，n に対して次のとおりに定義された関数 Ack (m，n) がある。Ack (1，3) の値はどれか。
Ack (m，n) ＝
- Ack (m−1，Ack (m，n−1)) （m＞0 かつ n＞0 のとき）
- Ack (m−1，1) （m＞0 かつ n＝0 のとき）
- n＋1 （m＝0 のとき）
- ア 3
- イ 4
- ウ 5
- エ 6
正解と解説を見る
正解: ウ
- ア: 3 は Ack(1, 1) の値です。
- イ: 4 は Ack(1, 2) の値です。
- ウ: Ack(1, 3) = Ack(0, Ack(1, 2)) = Ack(0, 4) = 5 なので、正しい答えです。
- エ: 6 は Ack(1, 4) の値です。
ポイント
定義に従って内側から計算します。
- Ack(1, 0) = Ack(0, 1) = 1 ＋ 1 = 2
- Ack(1, 1) = Ack(0, Ack(1, 0)) = Ack(0, 2) = 3
- Ack(1, 2) = Ack(0, Ack(1, 1)) = Ack(0, 3) = 4
- Ack(1, 3) = Ack(0, Ack(1, 2)) = Ack(0, 4) = 5