小さなことにこだわって：φの再帰的プログラム

http://yamada-kuebiko.cocolog-nifty.com/blog/2012/02/post-fd48.html
2012年2月 8日 (水)に「まだ黄金比：再帰性」というのを書きました↑

★その後、何となく居心地が悪くってね。
なぜかと言いますと
φ＝１＋（１／φ）
φ＝√（１＋φ）
というように、φが再帰的に書ける、という話をして、これは同義反復ではない、再帰だ、とちゃんと言ったのに・・・。
上のページでお示ししたプログラムは「ループ」で書いてしまいました。
どうも後味が悪い。
プログラム書きとしては、こだわってしまう。
｛こだわる、というのはあまり良い意味ではないのでして、つまらぬことにひっかかっている、ということです。最近、食いもの屋が「こだわりの」なんていっているのは、正直なところすごく恥ずかしいことです。小さなことにかかずりあっていないで、大きな「大道」をお行きなさい、うまいものを食わせる、のが本道でしょ、と思います。｝

プログラムで遊んで３０有余年、こだわっちゃった。

★式そのものが再帰的に書かれているのだから、プログラムもその式のように再帰的に書けばよかった、という気分がぐるぐると頭の中で回ってしまって。
すっきりするために、再帰的プログラムを書きました。
｛自分の気分を晴らすためなので、再帰的プログラムとはどういうものか、ということに興味がない方は、この記事は飛ばして下さい。｝
他人の自己満足なんか読まされるのはたまんないですよね。

「再帰的プログラム」ということに興味があったらお読みくださいますよう。

★まず、エクセルのＶＢＡでプログラムを書いてみましょう。

●φの連分数表現は下のようになります。
-----------------------------
Option Explicit

Sub main()
    Const LEBEL = 20
    Dim i As Integer

    For i = 1 To LEBEL
        Cells(i, 1).Value = phi(i)
    Next i
End Sub

Function phi(n As Integer) As Double
    If n = 1 Then
        phi = 1
    Else
        phi = 1 + 1 / phi(n - 1)
    End If

End Function
-----------------------------
「ｐｈｉ」という関数が再帰的関数になっています。
ｐｈｉの定義にｐｈｉを使っていますね。

ただ、再帰的なプログラムを書くときの絶対的な注意事項がありまして。
数学なら「以下同文」で無限の彼方へ飛んで行ってしまってもいいのですが、コンピューターではそうはいきません。メモリーは有限なので、無限は扱えません。
ですから、必ず「停止する点」を明らかにして、必ず停止する、ということを保証しなければいけないのです。
上のプログラムでは「『ＬＥＢＥＬ』の段数だけ再帰を潜り込んだら終わる」としています。
ＬＥＢＥＬの値を変えれば、何段潜るかは自由に設定できますが、とにかく無限は避けなければなりません。
｛昔はよく、無限ループを書いてしまって、泣く泣くリセットかけたものです。｝

●φの連根号表現
-----------------------------
Option Explicit

Sub main()
    Const LEBEL = 20
    Dim i As Integer

    For i = 1 To LEBEL
        Cells(i, 1).Value = phi(i)
    Next i
End Sub

Function phi(n As Integer) As Double
    If n = 1 Then
        phi = 1
    Else
        phi = Sqr(1 + phi(n - 1))
    End If

End Function
-----------------------------
同様に、再帰的な関数を書きました。
再帰呼び出し（recursive call）をうまく使うと、プログラムが簡素になってすっきりしますが、間違いも入り込みやすい表現ですから細心の注意を要します。

-----------------------------
DECLARE EXTERNAL FUNCTION phi

　　　　LET lebel=10
　　　　FOR i=1 TO lebel
  　　　　 　　PRINT phi(i)
　　　　NEXT i
END

EXTERNAL FUNCTION phi(n)
　　　　IF n=1 THEN
   　　　　　　LET phi=1
　　　　ELSE
   　　　　　　LET phi=1+1/phi(n-1)
　　　　END IF
END FUNCTION
-----------------------------
これは十進ＢＡＳＩＣでの再帰的プログラムです。
lebel = 20 で実行すると↓
-----------------------------
1
2
1.5
1.66666666666667
1.6
1.625
1.61538461538462
1.61904761904762
1.61764705882353
1.61818181818182
1.61797752808989
1.61805555555556
1.61802575107296
1.61803713527851
1.61803278688525
1.61803444782168
1.61803381340013
1.61803405572755
1.61803396316671
1.6180339985218
-----------------------------
こうなります。１．６１８０３・・・に近づいていきますね。

-----------------------------
DECLARE EXTERNAL FUNCTION phi

LET lebel=20
　　　　FOR i=1 TO lebel
   　　　　　　PRINT phi(i)
　　　　NEXT i
END

EXTERNAL FUNCTION phi(n)
　　　　IF n=1 THEN
   　　　　　　LET phi=1
　　　　ELSE
   　　　　　　LET phi=SQR(1+phi(n-1))
　　　　END IF
END FUNCTION
-----------------------------
連根号プログラム。

再帰呼び出しを身につけますと、プログラム書きとしては、少し腕が上がった気がするものなのです。
自己満足。

★フラクタル、という言葉をご存知でしょうか。
簡単に、自己相似図形といっておきましょう。
「自己相似」というからには、「再帰」がものすごく「ふさわしい」図形でして。
自分の中に自分を埋め込んでいく、という作業を続けるのです。
一時凝りましたっけね。面白いですよ。