非負の整数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
解説
正解は3です。
関数Ackは、自分自身を呼び出す再帰関数（アッカーマン関数）です。
小さい引数から順に値を求めていくと、確実に計算できます。
【計算】
Ack(1，0)はm＞0かつn＝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です。
【選択肢別解説】
1：× 3はAck(1，1)の値です。
Ack(1，3)はそこからさらに2回展開する必要があります。
2：× 4はAck(1，2)の値です。
Ack(1，3)はこれに1を加えた値になります。
3：○ 順に計算するとAck(1，3)＝5となります。
m＝1のときはAck(1，n)＝n＋2という関係になっています。
4：× 6はAck(1，4)の値に当たります。
Ack(1，3)の値ではありません。
【ポイント】
再帰の問題は、定義式のうちどの場合に当てはまるかを確認しながら、小さい値から積み上げると計算ミスを防げます。