再帰

 プログラムを作る場合、一連の手順をまとめて関数とすることがあります。これは言語の種類によって、メソッドとかプロシジャとかサブルーチンと呼ばれます。関数は親会社からみた下請け工場のようなもので、親会社から呼び出されて何らかの作業を行います。 そこで、その関数がその関数自身を下請けとして呼び出すことを再帰的な呼び出しというのですが、はじめて聞くとなんのことやら分からないでしょうね。
 簡単な例を挙げましょう。n!(階乗)というのは、1×2×3×…×n ですが、
   n! = (n-1)! × n
とも定義できます。言葉で表すなら「nの階乗とはn-1の階乗にnを掛けたものである」となります。なんだか変ですね。階乗を定義するのに階乗を使っています。このとき階乗が再帰的に呼び出されているということになります。
 普通こういうのは呼び出しが呼び出しを生み、いつまでたっても解決しないので許されないことです。でも上の場合、この定義に
   0! = 1
を加えることによって計算可能になるのです。0!が分かるなら1!は分かる。そうしたら2!が計算でき、3!、4!とどこまでも計算できますね。実際に再帰的処理を行うには、呼び出しがどこかで終わるという仕組みになっています。
 ソートのアルゴリズムで最も速いといわれるクイックソートや、パズルのハノイの搭を解くときに再帰の考え方は不可欠です。これは数学的に考えると非常にスマートな記述なんですが、コンピュータにとっては簡単な処理ではありません。というのは、関数の自分自身を呼び出すなんてことはできない相談で、実際には自分のコピーをいっぱい作って呼び出すのです。- Y.O. ---



→ IT用語 もくじ       → TOP へ