再帰的プログラム
例えばある関数の値を求めるときに、その関数自信を呼び出して値を計算するようなプログラム を再帰的プログラム!" #$と言う。
階乗
0 とする。の値を求めるには、 文や ! 文を用いて までの整数を 順番に掛けることにより求めることができる。
一方、 は次の関係を満たす。
の時
の時
この関係に基づいて の階乗を計算するプログラムを作ると次のようになる。
プログラム例 $%
)"!* + * , - "# " に必要なヘッダファイル -
" ."/3 - 関数 のプロトタイプ宣言 -
" ".0*/
2
" "#" 3
".4" 5 4/3
".46*4# 7"/3 - ここで入力される " は正整数と仮定する -
" 5 ."/3 - 関数 ."/ を呼び出し、その戻り値を " に代入 -
".46*O 5 6*9"4# "# " /3 - 答えの出力 -
" 3
;
" ." "/ - "O を計算する再帰的関数 -
2
." 55 /
" 3 - " が のときは を返す -
!
" "-."/3 - " , のときは "-."/ を返す -
;
このプログラムを"5%で実行したときの様子を図%に示す。"関数では "文で"に% が読み込まれるので、「" 5 ."/3」の所で、.%/が呼び出される。この時、関数."/では、
仮引数"の値に%が代入された形で、実行が開始される。"はでは無いので、! 文が実行さ れ、ここで、."/5.$/が再度呼びだされる。$回目に呼び出された関数."/では、その仮引 数"の値に$が代入された形で、実行が開始される。この時、"はでは無いので、! 文が実 行され、ここで、."/ 5 ./がまたまた呼び出される。%回目に呼び出された関数."/で は、その仮引数"の値にが代入された形で、実行が開始される。この時"はなので、文の 条件." 55 /が成立し、「" 3」により、戻り値で$回目に呼び出された関数."/にも どり、「" " - ."/3」.5「" $ - 3」/が実行される。これにより、戻り値$で
int main(void) {
int n, ans;
ans = f(n);
䈇䈇 }
int f(int n) { if (n == 1) return 1;
else
return n * f(n-1);
}
int f(int n) { if (n == 1) return 1;
else
return n * f(n-1);
}
int f(int n) { if (n == 1) return 1;
else
return n * f(n-1);
} 㼚㻌㻩㻌㻟㻌䜢ධຊ
f(n); f(3)䜢ฟ
n=3
f(n-1);
f(2)䜢ฟ
n=2
f(n-1);
f(1)䜢ฟ
n=1
||
1
||
2
||
2
ᡠ䜚್䛿㻝
||
2
||
3
||
6
ᡠ䜚್䛿㻞 ᡠ䜚್䛿㻢
||
6
㻝ᅇ┠䛾ฟ 㻞ᅇ┠䛾ฟ 㻟ᅇ┠䛾ฟ
図 ) 実行の様子
最初に呼び出された関数."/に戻る。そして、最初に呼び出された関数."/では、「" "
- ."/3」.5「" % - $3」/が実行され、戻り値(で"関数に戻る。"関数では、
この値.(/が変数" に代入される。
関数内で定義されたローカル変数や関数の仮引数として定義された変数は、関数が呼び出される たびに生成され、その関数の実行が終了すると消滅する。このため、"関数のローカル変数"#
最初に呼び出された関数."/の仮引数"# $回目に呼び出された関数."/の仮引数"# %回目に 呼び出された関数."/の仮引数"は互いに独立な変数であり、異なる値を保持することができる。
プログラム例$%の関数が"Oを正しく計算出来ることは数学的帰納法により証明できる。
【証明】
の時、この関数の戻り値は であり、 0 なので、正しく計算出来ている。
$ の時、この関数の戻り値が0であると仮定する。
/ の時、 なので、この関数の戻り値は / である。仮定より
0 なので、/ / 0/ 0となり、正しく/ 0が 計算出来ていることが分かる。
最大公約数
$つの正整数と の最大公約数 を求める問題を考える。ここで、簡単のために
と仮定する。整数の範囲で を で割ったときの商を # 余りを とすると.即ち、
/ /、次の性質が成り立つ。
のとき
のとき
演習 $& 上記の性質を証明せよ。次に、この性質に基づき、与えられたつの正整数の最大公約数 を求める再帰的プログラムを作成せよ。作成したプログラムを用いて、
を求めよ。
ヒント 1言語では、変数# の型が整数ならば、 を で割ったときの商と余りは、各々 #
6 で求めることができる。
この性質を繰り返し用いて最大公約数を求める方法を、<34'の互除法という。
選択の場合の数
" 個の中から重複を許さずに 個を選ぶ場合の数 を求める方法を考える。 は次の性 質を満たす。
またはのとき
/
のとき
演習 $' 上記の性質を証明せよ。次に、この性質に基づき、$と が与えられたときに を求 める再帰的プログラムを作成せよ。作成したプログラムは効率の良いプログラムと言えるかどうか 考察せよ。もし効率が悪いなら、どうすれば効率が改善できるかを考察し、より効率の良いプログ ラムを作成してみよ。
ハノイの塔
パズル「ハノイの塔」とは、次のようなパズルである。平面上に%本の棒が立っており、中央に 穴のあいた " 枚の円盤がある。" 枚の円盤の大きさは、すべて異なっている。今、図%./に示 すように、番目の棒に " 枚の円盤が大きさの順に.番大きい円盤が番下で、番小さい円盤 が番上/ 挿さっているものとする。円盤を枚ずつ別の棒に移動し、最終的に図%. /に示す ように、%番目の棒に " 枚の円盤が大きさの順に挿さっている状態にするには、円盤をどのよう に移動すれば良いかを求めるのがパズルである。ただし、円盤の移動には次のような制約がある。
棒の番上の円盤のみ別の棒の番上に移動できる。
ただし、自分より小さな円盤の上に置くことはできない。
棒 2
棒 3 棒
1 n = 4
棒 2
棒 3 棒
1
(a) 初期状態 (b) 最終状態
図 ) ハノイの塔
このパズルは、次のような考え方で解くことができる。今、! という関数で、棒
に挿さっている上から 枚の円盤を 棒 に移動させる方法を求める.出力する/ものと すると、
効率に関する議論や改善プログラムについては挑戦課題としますので、時間があれば考えて下さい。
!
のときは、「棒 の番上の円盤を棒 へ移動」と出力
のときは、
棒 の上から 枚の円盤を棒 へ移動
! !
棒 の番上の円盤を棒 へ移動
!
棒 の上から 枚の円盤を棒 へ移動
! !
となる。ここで、 は # 以外の棒である。
すなわち、 の時は、直接円盤を移動できるので、「棒 の番上の円盤を棒 へ移 動」と出力する。
のときは、図%$に示すように、
棒の上から枚目の円盤を棒に移動させるためには、棒の上から 枚の 円盤が邪魔になるので、ひとまずこれらの円盤を棒 に移動(退避)させる。このため に必要な円盤の移動方法は、! ! を呼び出すことにより求められる。
$ 次に棒の一番上の枚の円盤を棒に移動する。このために必要な円盤の移動方法 は、! を呼び出すことにより求められる。
% 最後に、最初のステップで棒 に退避させた 枚の円盤を棒に移動させれば良 い。このために必要な円盤の移動方法は、! ! を呼びだすことにより求め られる。
k = 4 from = 1, to = 3
from (=1) other (=2)
from (=1) to (=3)
other (=2) to (=3)
図) 円盤の移動方法
演習 $( ハノイの塔のパズルを解くプログラムを作成して実行せよ。また、枚の円盤のハノイ の塔のパズルを解くのに円盤の移動が何回必要か理論的に考察し、プログラムの実行結果と比較 せよ。
ヒント 枚の円盤のハノイの塔のパズルを解くのに必要な円盤の移動回数をとし、
と の関係.漸化式/を求め、その漸化式を解くことにより を求めることがで きる。
ヒント 作成したプログラムが正解を答えるかどうかを確かめるためには= " と言うプログラ ムを用いることが出来る。= " の使い方は、以下の通りである 。
=%===./6 = "
円盤の枚数 = % 円盤の枚数.以下/を指定
5 % 棒から棒%へ円盤を移動
5 $ 棒から棒$へ円盤を移動
5 % $ 棒%から棒$へ円盤を移動
5 % 棒から棒%へ円盤を移動
5 $ 棒$から棒へ円盤を移動
5 $ % 棒$から棒%へ円盤を移動
5 % 棒から棒%へ円盤を移動
5 終了
演習$(の実行結果を= "に入力することで、円盤の移動状況を確認することが出来る。
ヒント = "は>オプション付きで実行.= " >/すると、プロンプト.「円盤の枚数 5
」や「 5 」/を出力しないように作られている。このため、演習$(のプログラム
. "/の出力を
% 円盤の枚数を指定
% 棒から棒%へ円盤を移動
$ 棒から棒$へ円盤を移動
% $ 棒%から棒$へ円盤を移動
% 棒から棒%へ円盤を移動
$ 棒$から棒へ円盤を移動
$ % 棒$から棒%へ円盤を移動
% 棒から棒%へ円盤を移動
終了
のように作成し 、「 " P = " >」のようにパイプを用いて実行すると、"
の実行結果をアニメーションとして表示させることが出来る 。
下線部は説明であり、プログラムへの入力ではない。
+-を実行するためには、まず、最新の '.?5-パッケージを公式ホームページ-$$5@;;;669.$>
366A5B1- 1からダウンロードしてインストールし、次に、本演習のホームページから+-6をダウンロー ドし、「-1>+-+-6」でコンパイルして下さい。
下線部は説明であり、プログラムの出力では無い
人間にとっては分かりにくいが、、、
「&」は、左側のプログラムと右側のプログラムをパイプでつなぐためのものである。パイプでつなぐと、左側のプロ グラムの「標準出力」画面が右側のプログラムの「標準入力」キーボードに接続され、左側のプログラムの出力が右 側のプログラムの入力となる。