011: 「アッカーマンの深淵」のヒント

問題 / 解答

難易度: ☆☆

ヒント1

一般の A(m, n) をそのまま再帰関数にすると、呼び出しが深くなります。 この問題では m = 3 に固定されているので、A(0, n)、A(1, n)、A(2, n)、A(3, n) を順に整理します。

ヒント2

A(0, n) は定義から n + 1 です。 この式を使うと、A(1, n) は n + 2 になります。

ヒント3

A(2, n) は 2 * n + 3 になります。 したがって、A(3, n) は前の値から次の値を作る式にできます。

ヒント4

A(3, 0) = 5 です。 n > 0 では、A(3, n) = 2 * A(3, n - 1) + 3 になります。 ここから、A(3, n) = 2 ** (n + 3) - 3 と書けます。