7.3 非負整数を引数に取る再帰的関数

非負整数全体の集合 \(\mathbb{N}\) も再帰的データ型として理解できる。

定義 7.3.1

集合 \(\mathbb{N}\) は次の規則で再帰的に定義される:

\(0 \in \mathbb{N}\)
\(n \in \mathbb{N}\) なら、\(n\) の後者 (successor) \(n + 1\) も \(\mathbb{N}\) に属する。

この定義を示したのは、通常の数学的帰納法が定義 7.3.1 に関する構造的帰納法という特殊ケースに過ぎない事実を強調するためである。また、非負整数を引数に取る見慣れた再帰的定義も定義 7.3.1 によって正当化される。

7.3.1 非負整数を引数に取る再帰的関数の例

例 7.3.2[階乗関数]

この関数は \(n!\) と表記されることが多く、この表記は本書でも何度も登場する。ただ、ここでは \(\operatorname{fac}(n)\) と表記する。\(\operatorname{fac}(n)\) は次の規則で再帰的に定義できる:

\(\operatorname{fac}(0) ::= 1\)
\(\operatorname{fac}(n+1) ::= (n+1) \cdot \operatorname{fac}(n) \qquad (n \geq 0)\)

例 7.3.3[総和記号]

\(S(n)\) を \(\sum_{i=1}^{n}f(i)\) の省略記法とする。この \(S(n)\) は次の規則で再帰的に定義できる:

\(S(0) ::= 0\)
\(S(n + 1) ::= f(n+1) + S(n) \qquad (n \geq 0)\)

7.3.2 ill-formed な関数定義

関数を再帰的に定義するときに注意が必要な点は他にもある。大きな問題の一つは関数の定義が引数に取るデータ型の再帰的な定義に従っていないときに発生する。次に示すのは非負整数を引数に取る関数の定義のように見えて実際には定義でない規則である:

\[ f_{1}(n) ::= 2 + f_{1}(n-1) \tag{7.2}\]

この「定義」はベースケースを持たない。関数 \(g\) が規則 \(\text{(7.2)}\) を満たすとき、その値に定数を加えた関数も同じ規則を満たす。つまり規則 \(\text{(7.2)}\) は関数を一意に特定しない。では、次の規則はどうだろうか？

\[ f_{2} (n) ::= \begin{cases} 0 & n = 0 \text{ のとき} \\ f_{2}(n+1) & \text{それ以外のとき} \end{cases} \tag{7.3}\]

この「定義」はベースケースを持つものの、\(f_{2}\) は一意に定まらない。\(n = 0\) のとき \(0\) を返し、他の \(n\) の値に対しては同じ値を返す任意の関数が規則を満たす。つまり規則 \(\text{(7.3)}\) も関数を一意に特定しない。

典型的なプログラミング言語で \(f_{2}\) を計算する関数を書いて \(f_{2}(1)\) の評価を実行すると \(f_{2} (2)\) が再帰的に呼び出され、さらにそこから \(f_{2}(3)\) が再帰的に呼び出され、以下同様となって計算が停止しない。この「操作的 (operational)」アプローチでは、規則 \(\text{(7.3)}\) を \(n=0\) でのみ定義される部分関数 \(f_{2}\) の定義と解釈する。

次に示すのは「値が定まりすぎる」例である:

\[ f_{3}(n) ::= \begin{cases} 0 & n \text{ が } 2 \text{ で割り切れるとき} \\ 1 & n \text{ が } 3 \text{ で割り切れるとき} \\ 2 & \text{それ以外のとき} \end{cases} \tag{7.4}\]

この「定義」は一貫していない: \(f_{3}(6) = 0\) と \(f_{3}(6) = 1\) の両方が正しくなる。つまり規則 \(\text{(7.5)}\) は何も定義しない。

次に示す関数の定義について、数学者は長く考えてきた:

\[ f_{4}(n) ::= \begin{cases} 1 & n \leq 1 \text{ のとき} \\ f_{4}(n/2) & n \geq 1 \text{ が奇数} \\ f_{4}(3n+1) & n \geq 1 \text{ が偶数} \end{cases} \tag{7.5}\]

例えば、次の関係から \(f_{4}(3) = 1\) が分かる:

\[ \small f_{4} (3) ::= f_{4} (10) ::= f_{4} (5) ::= f_{4} (16) ::= f_{4} (8) ::= f_{4} (4) ::= f_{4} (2) ::= f_{4} (1) ::= 1 \]

全ての値が \(1\) に等しい定数関数は規則 \(\text{(7.5)}\) を満たす。しかし、規則 \(\text{(7.5)}\) を満たす関数が他に存在するかどうかは分かっていない。問題は三番目のケースで \(f_{4}(n)\) の計算に \(n\) より大きい値に対する \(f_{4}\) の値が必要となることで、このため \(\mathbb{N}\) に対する構造的帰納法が使えない。「規則 \(\text{(7.5)}\) を満たす関数は全ての値が \(1\) に等しい定数関数のみである」という主張は Collatzコラッツ予想 (Collatz conjecture) と呼ばれる。\(n\) が \(10^{18}\) 以下の非負整数のとき \(f_{4}\) は \(1\) に等しいことが確かめられている。

最後の例として Ackermannアッカーマン関数 (Ackermann function) を紹介する。これは二引数関数であり、極端に速く大きくなることが知られている。そのため Ackermann 関数の逆関数は非常にゆっくりとしか大きくならない ── その速度は \(\log n\), \(\log \log n\), \(\log \log \log n\), \(\ldots\) のいずれより遅いものの、上界は存在しない。この逆関数は Union-Find アルゴリズム (Union-Find algorithm) と呼ばれる有用かつ非常に高速な手続きの解析で姿を現す。このアルゴリズムは入力の長さに応じて線形に増加するステップ数で実行できると予想されていたものの、この「線形」には非常にゆっくりと増加する係数が付いていることが判明し、この係数が Ackermann 関数の逆関数にほぼ等しかった。これは実際にプログラムを書く上では Union-Find アルゴリズムの実行時間は線形と考えて問題ないことを意味する。なぜなら、その定数でない係数は理論的には無限に大きくなるのに対して、コンピューターが現実的に処理できる量の入力では常に \(5\) 未満であるからである。

Ackermann 関数は次の再帰的な規則によって定まる関数 \(A\) と定義される:

\[ A(m, n) ::= \begin{cases} 2n & m = 0 \text{ または } n \leq 1 \text{ のとき} \\ A(m - 1, A(m, n-1)) & \text{それ以外のとき} \end{cases} \]

この規則は奇妙な形をしている: \(A(m, n)\) の計算に \(n\) をずっと大きな値にした \(A\) の値が必要になる。規則 \(\text{(7.3)}\) が定める \(f_{2}\) で見たように、小さい引数に対する値が大きい引数に対する値に依存していると値の評価が停止しない可能性がある。ただ、Ackermann 関数の定義は問題ない。この事実の証明には多少の洞察が必要になる (問題 7.26)。