私が初めてプログラムを書き始めたころ、それは Basic で書いていたのだが、再帰を使いたいなどとは考えなかった。そんなものがあることも知らなかったのだ。私は Basic で考えていたのだ。私は反復アルゴリズムしか知らなかったのだから、再帰を使いたいなんて考えられるわけがない。
『ANSI Common Lisp』ポール・グレアム著、久野正樹・須賀哲夫訳より引用
再帰関数とは、名が示すように関数である。関数の中で再び自分自身を呼び出すという点が普通の関数と異なる。
再帰関数で重要な点は、
ということだが、それと同じくらい大切なことは、
ということである。再帰関数は再帰呼び出しをする再帰部分と、再帰呼び出しをしない基本部分（ベースケース）をもつ。
次の関数は、引数を 1 つとる再帰関数である（引数は 0 を含めた自然数と仮定）。この関数は引数から 0 までの整数の合計を返す。
function Sum(x: Integer): Integer;
begin
if x = 0 then
Result := 0
else
Result := x + Sum(x - 1);
end;
begin
Writeln(Sum(5));
Writeln(Sum(10));
Readln;
end.15 55
Sum 関数をもう一度みてみよう。
function Sum(x: Integer): Integer;
begin
if x = 0 then
Result := 0
else
Result := x + Sum(x - 1);
end;Sum 関数に渡された引数が 0 でなければ、
Result := x + Sum(x - 1);
が実行される。すなわち、
Sum(x - 1);
が実行されることにより、再び自分自身を呼び出すことになる。 よって、引数が 0 でなければ再帰呼び出しを行う再帰部分が実行される。
一方、引数として 0 が渡されるとき、
Result := 0;
が実行される。すなわち、引数が 0 であれば再帰呼び出しを行わない基本部分が実行される。
Sum 関数が正しく動作するかを調べるには、Sum 関数が受け取る引数がどんな値でも正しく動くかを調べればよい。
定義をもう一度載せる：
function Sum(x: Integer): Integer;
begin
if x = 0 then
Result := 0
else
Result := x + Sum(x - 1);
end;この場合、次の 2 点について調べる。
上記の定義は 1. を満足している。x が 0 のとき Sum 関数はただちに 0 を返す。つぎに、x が n でうまくいくとして、n+1 ではどうなるだろう。定義をみると、n+1 と Sum(n) を足したものが返される。仮定より Sum(n) がうまくいくので、n+1 もうまくいくことが分かる。これで調べなければいけないことは全部である。
上の再帰関数の説明は、ページ冒頭でもあげた『ANSI Common Lisp』を参考にして書いた。同書には再帰に対するイメージについて言及されているので、それを引用したい：
初めのうちは再帰は理解するのが難しいと思う人が多い。難しいと思ってしまうのは、主に関数に対して誤ったメタファ（比喩）をあてはめていることによる。人々は関数をマシンの一種ととらえがちである。原料がパラメータで届き、ほかの関数に下請けに出して処理し、最後に完成品を組み立てて、返り値として出荷する。関数に対してこのメタファをもっていると、再帰は不可能ということになる。マシンがどうやって作業を自分自身に下請けに出すのか？動作中のマシンにはそんな余裕などないじゃないかと思ってしまうことになる。
関数は進行しつつあるプロセスであると見る方が、メタファとしては適当であろう。再帰はプロセスの中では自然なものである。日常生活でも再帰的なプロセスをよく見る。たとえば、ヨーロッパ史における人口変化に関心をもっている歴史家を考えてみよう。資料を調べるプロセスは以下のようなものだろう。
- 1 つの資料を手に入れる
- 人口変化に関する情報を探す
- その資料がほかの役立ちそうな資料に言及していたら、ほかの資料を調べる
このプロセスは理解しやすいものだが、第 3 ステップにより同じプロセスが何度か適用されることがあるので、再帰的なプロセスになっている。
更新日:2004-11-23