« ホトケノザ | トップページ | まだやってる »

2012年2月10日 (金)

再帰呼び出し:Recursive call

まだやってます。

注意!:以下、再帰的なプログラムをいくつかお目にかけますが、本当は再帰的に書くよりも、ループで書く方が大抵の場合、速くてメモリーも節約できます。再帰で書いてはいけない例としてよく使われる話を敢えて書きますので、もし、プログラミングを始めたばかりでしたら、参考にしない方がいいですよ。

★さて、フィボナッチ数列の各項の比が黄金比に近づいて行くという話の延長戦です。

フィボナッチ数列というのは
1,1,2,3,5,8,13,21,34・・・
と続く数列です。

=1
=1
=Fn-1+Fn-2

一応、こういう定義にしておきましょう。(違ったスタイルの定義もありますが)

数列のこういう表現、高校で習うんですよね。漸化式です。

Fの定義にFを使っています。
ということは再帰的な定義ですね。
ということは、フィボナッチ数列を書きだすプログラムを書くときは、再帰的に書けるということでもありますね。
どうも、うずうずしてしまった。

↓これが十進BASICで再帰的に書いたフィボナッチ数列を書くプログラムです。
------------------------------
DECLARE EXTERNAL FUNCTION fib

FOR i = 1 TO 10
   PRINT i ;
   PRINT fib(i)
NEXT i
END

EXTERNAL FUNCTION fib(n)
IF (n = 1)OR(n = 2) THEN
   LET fib = 1
ELSE
   LET fib = fib(n-1) + fib(n-2)
END IF
END FUNCTION
------------------------------
fibという関数の中で、n  が 1 と 2 の時は関数値として1を返し、それ以外の時は前2項の和を返す、と書いてあります。定義通りですね。
これを実行すると↓
------------------------------
1  1
2  1
3  2
4  3
5  5
6  8
7  13
8  21
9  34
10  55
------------------------------
こういう数列が得られます。
ね、意図したものが得られました。ハッピー。
プログラムを書く楽しみというのは、これでして、意図したことがちゃんと実行されることに尽きます。
Cで書くときは、「return EXIT_SUCCESS」という一行をプログラムの最後に書いておいて、この行が実行されるとプログラムが終了するので、「成功裡に終わった」と呟いて(粋がって)喜ぶのです。

★せっかくここまで来ちゃったからなぁ。
再帰関数の入門みたいなのを書きたくなった。

多分一番有名なのは階乗ですね。

n!は普通は
n*(n-1)*(n-2)*・・・*2*1
こう定義されますが、

こんな定義も可能です。
n=0のときn!=1
n>0のときn!=n*(nー1)!
これが再帰的な定義です。階乗を定義するのに階乗を使いました。

プログラム化すると
------------------------------
DECLARE EXTERNAL FUNCTION fac

LET n = 10

FOR i = 1 TO 100
   PRINT i;
   PRINT fac(i)
NEXT i

END

EXTERNAL FUNCTION fac(n)
IF n = 0 THEN
   LET fac = 1
ELSE
   LET fac = n * fac(n-1)
END IF
END FUNCTION
------------------------------
0  1
1  1
2  2
3  6
4  24
5  120
6  720
7  5040
8  40320
9  362880
10  3628800
------------------------------
関数電卓では、普通10の99乗までが限界です。
69!=1.711224×10^98
となると思います。
70!はerrorでしょう。
では、ここまで読んで頂いた記念に、お土産を差し上げます。

69!=  171122452 4281413113 7246833888 1272839092 2705448935
          2036939364 8040923257 2797541406 4742400000 0000000000

70!= 1 1978571669 9698917960 7278372168 9098736458 9381425464
            2585755536 2864628009 5827898453 1968000000 0000000000

こんな数なんですよ~。
限界の外へ、一歩踏み出した気分を味わって下さい。
100!も計算しましたが、のせるのはやめます。
------------------------------

★ところで、ハノイの塔という有名なパズルあります。
詳細は私のHPが(相当に)詳しいです↓
http://homepage3.nifty.com/kuebiko/science/freestdy/Twr_Hanoi/Hanoi.htm

ここでは、手数を求める再帰的なプログラムをお目にかけます。
一般項は
=10^n-1
なので、これを使えば何のこともないのですけどね。
敢えて再帰的に書いてみました。
で、このパズル、普通64枚の板という設定なのですが、それでも、普通の関数電卓では指数表示になってしまって、きちんと全部書きだすのは難しい。(ウィンドウズのアクセサリの電卓を関数電卓にすると、2^64をフルに求めてくれますよ。)

せっかく十進BASICで書いていますから、1000桁モードでの結果を差し上げます。

------------------------------
DECLARE EXTERNAL FUNCTION hanoi

LET maisu = 64

FOR i = 1 TO maisu 
   PRINT i;
   PRINT hanoi(i)
NEXT i
END

EXTERNAL FUNCTION hanoi(n)
IF n = 1 THEN
   LET hanoi = 1
ELSE
   LET hanoi = 2 * hanoi(n-1) + 1
END IF
END FUNCTION
------------------------------
1  1
2  3
3  7
4  15
5  31
6  63
7  127
8  255
9  511
10  1023
 ・・・
64  18446744073709551615
 ・・・

100  126,7650,6002,2822,9401,4967,0320,5375
------------------------------
64枚でも
1844,6744,0737,0955,1615
1844京・・・です。

もし100枚の板でやったら、とんでもないことになります。
兆、京、垓を超えてしまった。
126穣・・・
(およそ400京年かかるようです・・・)

« ホトケノザ | トップページ | まだやってる »

理科おじさん」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/211707/53946840

この記事へのトラックバック一覧です: 再帰呼び出し:Recursive call:

« ホトケノザ | トップページ | まだやってる »

2018年9月
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30            
サイト内検索
ココログ最強検索 by 暴想
無料ブログはココログ