再帰的定義についてもう少し説明して下さい

> 再帰的定義の例のプログラムで、再帰からの脱出までは、

> 分かるような気がするのですが、

> 再び逆を追って、呼び出す過程が理解できません。

　 再帰はプログラムに書かれている順に，呼んで行きますが，戻るのはその逆になります。深い谷を順に下りながら降りていって，谷底にある宝物を取って，また順に上っていく感じです。再帰的アルゴリズムも参照して下さい。

　「再帰的アルゴリズム」の例にある，階乗関数を例にして説明しましょう。

' プログラム１
Function Kaijyou(n)
   If n = 0 then
      Kaijyou = 1
   Else
      Kaijyou = Kaijyou(n-1)*n
   End if 
End Function

このプログラムを使って，10! を計算する過程を考えてみます。例えば，このプログラムを実行した直後，実行画面で

Print Kaijyou(10)

とすると，以下のようになります。

この計算では，結果のみ表示されていますが，実際には，

Kaijyou(10)，Kaijyou(9)，Kaijyou(8)，Kaijyou(7)，Kaijyou(6)，Kaijyou(5)，Kaijyou(4)，Kaijyou(3)，Kaijyou(2)，Kaijyou(1)=1 （計算が出来た）

と計算していき，その結果を順次使って，

Kaijyou(2)=Kaijyou(1)*2=2

Kaijyou(3)=Kaijyou(2)*3=6

Kaijyou(4)=Kaijyou(3)*4=24

Kaijyou(5)=Kaijyou(4)*5=120

Kaijyou(6)=Kaijyou(5)*6=720

Kaijyou(7)=Kaijyou(6)*7=5040

Kaijyou(8)=Kaijyou(7)*8=40320

Kaijyou(9)=Kaijyou(8)*9=36280

Kaijyou(10)=Kaijyou(9)*10=362800

と計算し，最後の結果を値として返して，それが表示されています。

　上の結果を実際のプログラムで確認してみましょう。 プログラム１を少し修正して，次のプログラムにしました。

' プログラム２
Function Kaijyou(n)
   Print "n=";n      '<---ここを追加
   If n = 0 then
      Kaijyou = 1
   Else
      Kaijyou = Kaijyou(n-1)*n
   End if 
End Function

このプログラムは Kaijyou が呼ばれた直後に，それぞれ，n を値を表示します。これも，このプログラムを実行した直後，実行画面で

Print Kaijyou(10)

とすると，以下のようになります。

この結果から，実際に，

Kaijyou(10)，Kaijyou(9)，Kaijyou(8)，Kaijyou(7)，Kaijyou(6)，Kaijyou(5)，Kaijyou(4)，Kaijyou(3)，Kaijyou(2)，Kaijyou(1)

と呼ばれていることが分かります。最後の3628800が返された計算結果です。

それでは，次に，順次戻ってくる状況を表示してみましょう。

そのために，プログラム２を少し修正します。

' プログラム３
Function Kaijyou(n)
   Print "n=";n
   If n = 0 then
      Kaijyou = 1
   Else
      K = Kaijyou(n-1)*n            'この３行を変更
      Kaijyou = K                   '
      Print "n=";n;Tab(10);"K=";K   '
   End if 
End Function

　この修正は少しデリケートです。それは，上のプログラムで

• Kaijyou は関数名なので，Kaijyou = *** の形でしか使えない。

• Kaijyou(n-1) はプログラムの核心で，それを２度呼ぶことはできない。

ということがあります。そこで，一度，別変数 K で値を保存してから，表示とKaijyou への代入を行っています。これも，このプログラムを実行した直後，実行画面で

Print Kaijyou(10)

とすると，以下のようになります。

n=0 になってからはじめて，値を返す状況になり，順次戻ってくる様子を表しています。

　この階乗関数の場合は，n=0 まで下がり，それから n=10 に上るという単純な流れですから計算量も比較的少なく，使用可能なアルゴリズムです。

　「再帰的アルゴリズム」の例で扱った，フィボナッチの数列の計算についても考えてみます。プログラムは次の通りでした。

' プログラム４
Function Fib(n)
   If ((n=1) or (n=2)) then
      Fib=n
   Else
      Fib = Fib(n-1)+Fib(n-2)
   End if
End function

これも上と同様な，方針でプログラムを変更してみると次のようになります。

' プログラム５
Function Fib(n)
   Print "n=";n
   If ((n=1) or (n=2)) then
      F=n
      Fib=F
      Print "n=";n;Tab(10);"F=";F
   Else
      F = Fib(n-1)+Fib(n-2)
      Fib = F
      Print "n=";n;Tab(10);"F=";F
   End if
End function

これも，このプログラムを実行した直後，実行画面で

Print Fib(5)

とすると，以下のようになります。

この場合，階乗関数に比べて複雑です。これは

F = Fib(n-1)+Fib(n-2)

のところで，２回再帰を行っていることによります。一度呼ぶたびに２つの再帰呼び出しが起こります。再帰は繰り返されますから，これは倍々に呼び出しが増えることになります。

　今の場合は一筋に谷に向かって降りて上るのではなく，一段降りるたびに道が枝分かれし，結果を得るためにはその道をすべてたどり尽くす必要があります。ですから，この計算はアルゴリズムとしては良くないものです。

Print Fib(10)

でも，もうかなりの計算です。

　フィボナッチの数列の場合，再帰を使わない方法でプログラムが書けますから実は，この計算は無駄だったわけです。

これに対して，ハノイの塔の計算は，むしろ再帰が最適でした。これはハノイの塔の計算が実はそれだけ複雑であることを示しています。