第 V 部 再帰方程式

再帰方程式 (recurrence) は実数列を表現する。最初の数項は明示的に与えられ、それ以外の項は以前の項から計算する方法が与えられる。自明な例として、実数列 \(1\), \(2\), \(3\), \(\ldots\) を表現する再帰方程式を次に示す:

\[ \begin{aligned} T_{1} &= 1 \\ T_{n} &= T_{n-1} + 1 \qquad (n \geq 2) \end{aligned} \]

一つ目の式は初項が \(1\) だと定め、二つ目の式は「\(2\) 番目以降の項は、一つ前の項より \(1\) だけ大きい」と定める。

再帰方程式は強力なツールである。本章では再帰的アルゴリズムの性能解析における再帰方程式の利用に焦点を当てるものの、この他にも特定の性質を満たす構造の数え上げや乱択アルゴリズムの解析など、情報科学で再帰方程式が利用される場面は多くある。さらに第 14.4 節で触れたように、物理科学の問題の解析でも用いられる。

再帰方程式は実数列の表現としてあまり有用でない。例えば「第 \(100\) 項の値は？」「漸近的な増加速度は？」といった簡単な質問の解答を再帰方程式だけから得る一般的な方法は存在しない。そのため再帰方程式が与えられたときは、それを解く ── 第 \(n\) 項を表す閉形式の式を見つける ── ことが典型的な目標となる。

本章では再帰方程式を解くための一般的な手法を二つ紹介する:

これらの手法はどちらも任意の再帰方程式に適用できるものの、解を得るには「ひらめき」が ── ときには現実的でないほど賢い洞察が ── 必要になる。これと対照的な特徴を持つ、情報科学で頻繁に表れる大きな再帰方程式クラスも本章で紹介される:

これらのクラスに含まれる事実上全ての再帰方程式は機械的な手順で解くことができる: レシピに従えば解が必ず求まる。ただし欠点として、多少の計算が必要になる。推測検証と定義代入を使うときの「分かった！」は、計算が終わった後の「はぁ」に置き換わる。

本章の最後では、幅広い再帰方程式の解の評価に利用できる、計算の一切必要ない手法を紹介する。この手法は、例えばアルゴリズムの設計で有望なアプローチと無価値な思い付きを見極めるのに役立つ。

再帰方程式は情報科学で多用される考え方を数式で表したものと言える。それは「大きな問題をより小さな問題に帰着させ続け、最終的に簡単なベースケースに帰着させる」という考え方である。同じ考え方は数学的帰納法による証明や再帰的アルゴリズムでも使われている。本章で見るように、これら三つの概念は上手くかみ合う。例えば、再帰的アルゴリズムの実行時間を再帰方程式で表し、その解の正しさを数学的帰納法で検証するといった状況があり得る。

広告