再帰を見てみよう

再帰を一言で言うと、自分自身の中から自分を呼び出すことです。ん?、いったいどういうことだ?

例えば、階乗を例にして見ますと10 の階乗は、10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 です。これは、10 ! = 10 * ( 10 - 1 ) ! で表せます。また、ここでの ( 10 - 1 ) ! は ( 9 ) ! ということですので、9 ! = 9 * ( 9 - 1 ) ! で表せます。ということは、最初の式に戻って、10 ! = 10 * ( 9 * ( 9 - 1 ) ! ) ということになります。なにかパターンが見えてきましたね、どうやら n * ( n - 1 ) ! が続いてるだけみたいです。関数の中でまた関数を呼べば出来そうです。早速やってみましょう。ボタンと、Standard ページにある ListBox をフォームに貼り付けて下さい。以下のコードを書いて下さい。

function Fact(i: Integer): Integer;
begin
  if i = 0 then // これがないと無限に続いちゃいます
    Result := 1 
  else
    Result := i * Fact(i-1);
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Arr: array[0..9] of Integer;
  i: Integer;
begin

  for i := 0 to 9 do
    Arr[i] := Fact(i);

  for i := Low(Arr) to High(Arr) do
    ListBox1.Items.Add(IntToStr(i)+'! = ' + IntToStr(Arr[i]));
end;

関数 Recursion の中から、さらにまた Recursion を呼び出しています。これが、再帰の構造になります。図にしますと、以下のようになります。

これは、i が3の場合です。

このように、関数の中から、さらにまたその関数を呼び出すことにより再帰が成り立っています。

ちょっと一言: プログラムで、整数を使う時いつも Integer を使っていますが、これには、扱える値に限りがあります。-2147483648 〜 2147483647 までが、Integer の扱える値となっています。


up next
Last update: 2002/3/7