平成30年度 春期 午前 問5

✓ これが正解ウ5

解説

内側から順に展開すると Ack(1, 3) は 5 になります。

設問は、非負の整数 m と n について三通りに場合分けされた関数について、Ack(1, 3) の値を求めさせています。再帰の問題で迷わない手順は、まず止まる条件を書き出し、次に内側から順に潰し、最後に外へ戻すことです。止まる条件は m が 0 のときで、そのとき値は n に 1 を足したものになります。Ack(1, 3) は m も n も 0 より大きいので Ack(0, Ack(1, 2)) となり、同じ形をたどって Ack(1, 2)、Ack(1, 1)、Ack(1, 0) へ降りていきます。Ack(1, 0) は n が 0 の場合に当たるので Ack(0, 1) となり、その値は 2 です。ここから外へ戻すと Ack(1, 1) が 3、Ack(1, 2) が 4、そして Ack(1, 3) が 5 と求まります。並びを見ると Ack(1, n) は n に 2 を足した値になっており、n が 3 のときに 5 となることが検算としても確かめられます。

ほかの選択肢はなぜ違うのか

• ア3：降りていく途中で二段手前にとどまったときの数です。最後まで戻しきる前の段階であり、外へ戻す操作が二回ぶん残っています。
• イ4：外へ戻す途中の段階で止めたときに現れる数です。もう一段だけ戻す操作が残っており、最後の一手を省くとこの値のまま終わってしまいます。
• エ6：一段だけ多く進めてしまった場合の数です。n に 2 を足すという並びに照らすと、n が 4 のときの値に当たり、設問が指定した引数を越えています。