単純にして任せる

再帰 (recursion) は特に強力な帰着です。大雑把に言うと、次のように説明できます:

• もし問題のインスタンスを直接解くことができるなら、直接解く。
• そうでなければ、問題を同じ問題のよりシンプルなインスタンスに帰着させる。

自分自身を参照する部分が分かりにくいなら、他の帰着と同じように、小さいインスタンスを別の人が解いてくれると想像するとよいでしょう (この別の人のことを再帰の妖精 (Recursion Fairy)と呼ぶのが私のお気に入りです)。問題を解くためにすべきなのは、問題を単純にする、あるいはそれが不必要/不可能な場合には直接解く、それだけです。小さくなった問題は再帰の妖精が解いてくれます。どうやって解くかは私たちの知ったことではありません¹。数学をよく知っている読者は再帰の妖精のことをもっと正式な名前で呼ぶかもしれません: 帰納法の仮定と。

再帰的な手続きが正しく動くためには、ある簡単な条件を満たす必要があります: 単純なインスタンスをたどっていったときに無限列ができてはいけません。つまり、再帰的な帰着はいずれベースケースにたどり着かなければなりません。ベースケースとは再帰でない方法で解ける簡単なインスタンスのことです。もしベースケースが存在しなければ、再帰的なアルゴリズムは永遠にループしてしまいます。この条件を満たすために最もよく使われるのは、問題を (複数の) 小さなインスタンスに帰着させる方法です。例えば \(n\) 個の頭を持つドラゴンを倒す再帰的な戦略を考えているとしましょう。このとき、再帰的に呼ぶ問題は頭の数が \(n\) 個より真に小さいドラゴンに対する問題である必要があります。もちろん \(n=0\) でドラゴンが頭を持っていないときには再帰的な呼び出しができなくなる ――頭の数が負のドラゴンは存在しません！―― ので、この場合は頭の無いドラゴンを直接倒すことになります。

再帰の例は農民の掛け算アルゴリズムで既に出てきています。つまり、次の再帰的な等式 (再帰方程式) です: \[ x \times y = \begin{cases} 0 & \text{if } x = 0 \\ \lfloor x / 2 \rfloor \times (y + y) & \text{if } x \text{ が偶数} \\ \lfloor x / 2 \rfloor \times (y + y) + y & \text{if } x \text{ が奇数} \\ \end{cases} \] この再帰方程式はアルゴリズムとして次のようにも表現できます:

怠惰なエジプトの書記官がこのアルゴリズムを実行するときは、まず \(x^{\prime}\) と \(y^{\prime}\) を計算し、部下の書記官に \(x^{\prime}\) と \(y^{\prime}\) の積を計算するように頼み、最後に必要ならば部下からの答えに \(y\) を足して終わります。\(x^{\prime} < x\) であり、単調に減少する正の整数の数列はいずれ \(0\) になることから、部下に渡される問題はより単純なものだと言えます。部下が \(x^{\prime} \cdot y^{\prime}\) をどう計算するかは上司の知ったことではありません (あなたが気にする必要もありません)。

1. 私が学部生だったときは再帰の妖精ではなく "エルフ" に再帰を任せていました。年を取った靴職人が仕事を終わらせないままベッドに入って翌朝目を覚ますと、エルフ ("Wichtelmänner") が靴を完成させていたというグリム童話に出てくるあのエルフです。私よりも幻覚剤に精通した人なら、この "Rekursionswichtelmänner" のことを Terence McKenna (テレンス・マッケナ) の言葉を借りて「自己改変する機械仕掛けのエルフ (self-transforming machine elves)」と表現するかもしれません。^[return]