┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃.&&&& **** %%%%. JavaScript&Javaで目指そう！基本情報技術者試験 ┃
┃&&&&&&******%%%%%% 執筆＆編集 斎藤末広 suehiro@he.mirai.ne.jp ┃
┃'&┃&''*┃*''%┃%' 発行 江口昌宏 ＊＊＊ ┃
┗━┻━━┻━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
広告募集:http://www2.odn.ne.jp/~egu33/jmaga/java-maga.html
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
第１４号 2002/03/0x
再帰関数
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
プログラムを作成する上での注意事項：
Windows とIE を前提としています。
拡張子を表示するに設定してください。
-------------------------------------------------------------------------
▼ 再帰とは
第１３号のJマガで，1 から n までの整数を順番に足しているプログラムを扱い
ました。
例 j13-01 関数サンプル
関数 j13-01.htm
ここで，xtasu関数の部分だけ注目します。
これは，1 から x までの整数を足しこんでいっています。プログラムでは，
ループを使って，x 回繰り返すと書いています。
もし，１から１０までの合計をこれを手で計算するときは，
1 + 2 + 3 + ... + n
と計算するのが普通です。このやり方を分析してみます。
1 + 2 + 3 + ... とやるのは，1 に 2 を足して，3。それに，3 を足して，6。
それに，... とやるわけです。つまり，xtasu(2) は，xtasu(1)+2で，xtasu(3)は，
xtasu(2) +3 です。このやり方をJavaScripで書くと
となります。これを x 回 for 文で繰り返しながら合計を出していくプログラム
と比較すると，for 文の繰り返しの方が分かりやすいかもしれません。しかし，
x = 1 のときは，xtasua(1) は，1
x = 2 のときは，今計算した，xtasu(1) に 2 を足す
x = 3 のときは，今計算した，xtasu(2) に 3 を足す
とプログラムを読み取りをすると簡単なプログラムに見えます。
この関数が，プログラムの名で使用されるときは，document.write(xtasu(10));
のように使用されるので，コンピュータ内部では，そのつど，順に，
xtasu(10) = xtasu(9) + 10
xtasu(9) = xtasu(8) + 9
xtasu(8) = xtasu(7) + 8
xtasu(7) = xtasu(6) + 7
xtasu(6) = xtasu(5) + 6
xtasu(5) = xtasu(4) + 5
xtasu(4) = xtasu(3) + 4
xtasu(3) = xtasu(2) + 3
xtasu(2) = xtasu(1) + 2
xtasu(1) = 1
ここで，xtasu(1) = 1 が分かったので，逆戻りして，
xtasu(2) = 1 + 2 = 3
xtasu(3) = 3 + 3 = 6
xtasu(4) = 6 + 4 = 10
xtasu(5) = 10 + 5 = 15
xtasu(6) = 15 + 6 = 21
xtasu(7) = 21 + 7 = 28
xtasu(8) = 28 + 8 = 36
xtasu(9) = 36 + 9 = 45
xtasu(10) = 45 + 10 = 55
と計算します。xtasu(1) まで行って，終点があって，そこから，帰ってきて
xtasu(10) の答えがわかります。
このように，再び帰ってくるので，再帰（さいき）といいます。この場合は，
＠関数を再帰的に定義した」といわれます。この再帰を利用した関数を再帰関数，
再帰を利用したプログラムを再帰プログラムと呼ぶます。
-------------------------------------------------------------------------
▼ 再帰を可能にするには，
再帰関数は，自分で自分を利用しています。xtasu(10) = xtasu(9) + 10のよう
に，xtasu(10) を求めるために，xtasu(9)を利用しています。そのため，関数の実
行において，関数が，自分で自分を呼ぶことを可能にするからくりが必要です。
PASCAL，C，VB, JavaScriptやJavaではこれが可能です。COBOL のような言語では，
このような再帰関数は，一般的に実現が困難です。
再帰関数の実行において，
xtasu(10) = xtasu(9) + 10
xtasu(9) = xtasu(8) + 9
xtasu(8) = xtasu(7) + 8
xtasu(7) = xtasu(6) + 7
xtasu(6) = xtasu(5) + 6
xtasu(5) = xtasu(4) + 5
xtasu(4) = xtasu(3) + 4
xtasu(3) = xtasu(2) + 3
xtasu(2) = xtasu(1) + 2
xtasu(1) = 1
もどって，
xtasu(2) = 1 + 2 = 3
xtasu(3) = 3 + 3 = 6
xtasu(4) = 6 + 4 = 10
xtasu(5) = 10 + 5 = 15
xtasu(6) = 15 + 6 = 21
xtasu(7) = 21 + 7 = 28
xtasu(8) = 28 + 8 = 36
xtasu(9) = 36 + 9 = 45
xtasu(10) = 45 + 10 = 55
のような計算が内部で実行されました。コンピュータが，xtasu(10)を実行したと
きには，「xtasu(9)の答えが分かったら，それに10を足す」ということを記憶して，
xtasu(9)の計算に移ります。xtasu(9)の計算をするときに，xtasu(10)の記憶を消
さないために，xtasu()という関数は，実行するたびに，途中結果をそれぞれ残し
ておく必要があります。この途中結果を残すというからくりが，再帰関数のため
に必要です。
-------------------------------------------------------------------------
▼ 試験にこう出た
その１
プログラムの構造に関する次の記述の下線部 a〜d に，誤りが一つある。誤り
の箇所と正しい字句の適切な組合せはどれか。
自分自身を呼び出して使うことができるサブルーチンは，a 再帰的 であると
￣￣￣￣
いう。このようなサブルーチンを実行すると，局所変数，b 仮引数 及び戻り番
￣￣￣￣
地の格納領域が c スタック に確保され，d FIFO (First In First Out) 方式で
￣￣￣￣￣￣ ￣￣￣￣￣￣￣￣￣￣￣￣￣￣
制御される。
┌───────┬────────────┐
│ 誤りの箇所 │ 正しい字句 │
┌─┼───────┼────────────┤
│ア│ a │再入可能 │
├─┼───────┼────────────┤
│イ│ b │実引数 │
├─┼───────┼────────────┤
│ウ│ c │待ち行列 │
├─┼───────┼────────────┤
│エ│ d │LIFO (Last In First Out)│
└─┴───────┴────────────┘
■キーワード■ プログラム構造，再帰，引数，スタック，キュー，FIFO
■解答■
ネットワークスペシャリスト午前平成１２年問５０
┌───────┬────────────┐
│ 誤りの箇所 │ 正しい字句 │
┌─┼───────┼────────────┤
│エ│ d │LIFO (Last In First Out)│
└─┴───────┴────────────┘
その２
n の階乗を再帰的に計算する関数 F(n) の定義において，次の記述中の a に
入れるべき式はどれか。ここで，n は非負の整数とする。
n ＞ 0 のとき，F(n)＝【 a 】
n ＝ 0 のとき，F(n)＝ 1
ア F(n)×F(n−1)
イ n×F(n−1)
ウ (n−1)×F(n)
エ (n−1)×F(n−2)
■解答■
一種午前平成１２年問１２
イ n×F(n−1)
------------------------------------------------------------------------
▼ 次号の予定
簡単なアルゴリズム
感想は，斎藤まで，suehiro@he.mirai.ne.jp
広告等のお問い合わせ：＊＊＊
------------------------------------------------------------------------
▼ 誤字・脱字等の修正，プログラムの修正など，以下の場所で確認できます。
過去の修正版等
http://www.mirai.ne.jp/~suehiro/java/jmaga/
登録・削除および広告の案内
http://www2.odn.ne.jp/~egu33/jmaga/java-maga.html
------------------------------------------------------------------------
▼ 著作権について
このメールマガジンで公開しているプログラムソースは，著作権を当方スタッ
フが所有しますが，商用を含めて，再利用，改変，発表を制限しません。
本文に関しては，斎藤末広が著作権を所有します。再利用に関しては，承諾を
必要とします。
------------------------------------------------------------------------
▼アンケート（以下を返信してください）
この号のＪマガは役立ったあるいは勉強になりましたか？
該当するものだけ残してください。
5: 大いに，YES
4: YES
3: 普通
2: NO
1: 大いに，NO
その他