茨城大学 工学部 知能システム工学科 井上 康介 E2棟801号室 アルゴリズムとデータ構造 講義スライド 3 再帰 茨城大学 工学部 知能システム工学科 井上 康介 E2棟801号室

第4章：再帰 解くべき問題によっては，以下の考え方が有効である： 解くべき問題を「同じ解き方で解ける，よりサイズの小さな副問題」に分解し，先に副問題を解く 例）n ! を求める． n ! = n・(n - 1) ! である  先に (n - 1) ! が求まれば，それを n 倍すればよい  n ! を求めるのと (n - 1) ! を求めるのは同じ手順 この考え方でプログラムを作るとどうなるだろうか…？  何が起こるかを脳内シミュレーションしてみる  n ! を求める関数を kaijo(n)とし，これを main() から呼び出すシナリオを考えよう

第4章：再帰 2! は 2 です． main() kaijo(2) kaijo(1) kaijo(0) 2 ! を表示したい 画面表示 待機中 2 を返す 記憶の棚 (スタック領域) 呼出 2 ! = 2・1 ! だな kaijo(2) kaijo(1) kaijo(0)の返事待ち 返事が来たら1倍して返す 待機中 1 を返す 呼出 1 ! = 1・0 ! だな kaijo(2) kaijo(1)の返事待ち 返事が来たら2倍して返す kaijo(1) 待機中 1 を返す 呼出 定義上 0 ! = 1 だ main() kaijo(2)の返事待ち 返事が来たらそれを表示 kaijo(0)

2 ! は 2・1 ! だから，kaijo(1)を呼び出し， 返ってきた値を 2 倍して main()関数に返す 第4章：再帰 この例では，2 ! を計算するために呼び出された関数 kaijo(2)の内部処理では， ということを行った． つまり，「 2 ! を求める」という問題を「1 ! を求める」という 部分問題 に分解した．そして，それらの問題は 同じ手順で解ける問題 となっている  kaijo という名前の関数が，その内部処理において， 　同じ kaijo という名前の関数を呼び出す構造 である！ 2 ! は 2・1 ! だから，kaijo(1)を呼び出し， 返ってきた値を 2 倍して main()関数に返す

第4章：再帰 関数 kaijo() の内部で自分自身 kaijo() を呼び出すことを，再帰呼出 (recursive call) という． kaijo(n) の処理では kaijo(n-1) が呼び出され， kaijo(n-1) では kaijo(n-2) が呼び出される. これが無限に続いてはならないので，必ず脱出口として停止条件が必要となる． 階乗の計算においては，0 ! = 1 が停止条件となる． long kaijo(int n) { if (n==0) return 1; else return n * kaijo(n-1); }

第4章：再帰 再帰呼出をしたとき，コンピュータ上では何が起こる？ kaijo(n) の中で kaijo(n-1) を呼び出した時点では，kaijo(n) の作業はまだ実行途上であり，kaijo(n-1) の値をもらうまでは仕事を続行できない状態である (制御が kaijo(n-1) に移されてしまう)．さらに，kaijo(n-1) の方では kaijo(n-2) をもらうまで仕事が中断する． 「現在中断している仕事の情報」をどこかで憶えておかないといけない．その情報とは，関数ごとのリターンアドレス (制御を戻す位置)，引数，ローカル変数である． コンピュータ上では，これらの情報がスタック (第5章) としてメモリ空間上に積み上げられる (教科書 p.167の図4.2)．つまり，再帰呼出を繰り返すたびにメモリが消費されていく．これにより，空間複雑度 が増える．

第4章：再帰 さらに，コンピュータが関数を呼び出すとき，一定の処理時間がかかる．これを 関数呼び出しのオーバーヘッド と呼ぶ．これにより，時間複雑度 も増加する． つまり，再帰呼出はメモリ消費量・実行時間の双方について，効率をいくぶん下げるものと言える． しかし，処理するべき問題やそこで扱うデータ構造が再帰呼出に適したものであるときは，再帰呼出を使った関数にすることが 自然 であり，プログラムも シンプル なものとなる． 一般的に，再帰呼出を使った関数はテクニカルであり，実行したときに何が起こるかをきっちり考えるのが難しいことがある．

4-1 再帰の簡単な例 教科書 p.168 のコードが先程の階乗の再帰的な関数． ただし，返値が long 型となっているのは，一般に階乗は非常に大きい数になるから． 4行目で return 1L; とあるが，これは return (long)1; と同じ意味で，long 型への キャスト である． long kaijo(int n) { if (n==0) return 1L; else return n*kaijo(n-1); }

4-1 再帰の簡単な例 フィボナッチ数列：1, 1, 2, 3, 5, 8, 13, 21, 34, … 第 n 項は第 n-1 項と第 n-2 項を加えたもので，第 1 項と第 2 項は 1 である．つまり， この場合，関数の中で 2つの再帰呼出 を行う (p.171)． fib(5)を呼び出すと，fib(4)+fib(3)を計算しようとする．とりあえず fib(5)の現在の状態をスタックに保存して，fib(4)を呼びだし，そちらに制御を移す．fib(4)では，fib(3)+fib(2)を計算する．いったん fib(4)の状況をスタックに保存して fib(3)を呼び出して結果待ち．fib(3)では…

4-1 再帰の簡単な例 組み合わせ nCr も再帰的に処理できる．つまり，より小さな n や r に関する問題に分解できる． 多項式の値を効率的に求める Hornerの方法 でも，再帰的に問題を解ける． ただし，再帰呼出において，係数の列 {a1, …, aN} を渡してやる必要がある (教科書 p.174 のコードでは，係数列を格納した配列の先頭へのポインタを渡している)．

ハノイの塔 再帰の問題でよく取り上げられる例題． 以下のように3本の棒 a, b, c が立っている．棒 a に，大きさの異なる n 枚のドーナツ状の板が下から大きい順に刺さっている．これを1枚ずつ移動させて棒 b に移す． ただし, 途中で小さい板の上により大きな板が積まれてはならない． 棒 c は作業用に使う． a b c

ハノイの塔 板が1枚しかないときは，考えるまでもない． a b c

ハノイの塔 板が2枚の場合, いきなり板 1 を目的地の棒 b に持って行ってしまうと, どうにもできなくなる． そこで，邪魔な板 1 を作業用の棒 c にいったん待避させ，板 2 を棒 b に持って行った上で，板 1 を板 2 の上に重ねる． 邪魔者である板 1 を いったん脇にどけてから， 板 2 を目的地へ動かし，その上に板 1 を戻す． a b c

ハノイの塔 では，n 枚の場合はどうか？ n 枚全体を a  b へ移すという問題を， (1) 上に乗る n-1 枚を a  c へ (3) n-1 枚を c  b へ という問題に分解すること ができる． (1)，(3) は,「同じ手順で解けるサイズの小さい問題」である． 　　　 再帰的解決が可能 a b c n 枚目 n-1 枚の邪魔者

ハノイの塔 さて，プログラムとしてどう記述するか？ hanoi(n,k,l)：n 枚の板を棒 k から棒 l へ移す関数 この関数では，上に乗る n-1 枚の板を残った一つの棒 m へ移動し，上が空いた n 枚目の板を棒 l へ移動した後，棒 m へ移しておいた n-1 枚を棒 l へ移動すればよい． n-1 枚の板の移動は再帰呼出 hanoi(n-1,k,m)および，hanoi(n-1,m,l) により実現できる． 終了条件として，n = 0 の場合は「何もしない」だけ． ソースコードは p.194 にあるので，各自目を通しておくこと．頭で考えようとすると非常に難しいように思える問題が，再帰呼出の利用によって，たった5行の関数になっている．これが再帰呼出の威力である．

クイック・ソート 実用上，最も速いソートアルゴリズムといわれている．quick sort と呼ばれるゆえんである．別名 分割ソート． クイック・ソートの基本原理は,「長距離の値同士を交換する方が効率的である」という発想である．例えば， 70 20 80 50 40 60 30 10 というデータがあるとき，70-20 の交換 よりも 70-10 の交換 の方が，ソートに対して 大きな寄与 を持つ． 基本的手順：配列中の適当な値 (これを 軸 と呼ぶ) を選び，軸より小さな値全てを配列の左側に，軸より大きな値全てを軸の右側に集め，「軸より小さいグループ」と「軸より大きいグループ」に 分割 する． それぞれのグループに対してクイック・ソートを行う． p.206～211

クイック・ソート 軸の選択方法は様々にあり得るが，最も安直な方法は，データ列の先頭を選択すること． 軸に対して，データ列の分割は以下のように行う．  左端の位置を i，右端の右隣の位置を j とする． i を右に動かしていき，軸以上の値の位置で止める． j を左に動かしていき，軸以下の値の位置で止める． i >= j なら⑥へ． i の位置のデータと j の位置のデータを交換して②へ． j の位置のデータを軸 (左端) と入れ替える．      left right 41 21 24 36 76 11 45 19 21 41 64 21 64 69 19 45 76 36 軸 軸 i i i i i i j i j j j j j 小さいグループ 大きいグループ left right left right 再帰呼出 (=j-1) (=j+1) 再帰呼出

クイック・ソート 再帰呼出の終了条件 (脱出口) は, 「ソート対象の長さが2以上 (left < right) でないときは何もせずに返る」 なぜなら，ソートの対象データ数が 0個あるいは 1個であるときは，何もしなくて良いから． 例えばデータ数 2 のクイック・ソートの結果は，軸の片側にデータが 1個，反対側にはデータが 0個の状態になり，次回の再帰呼出ではどちらも何もしない． 軸を left と right の中央のデータ位置 (left+right)/2 とすることもできる．この場合，軸も交換の対象に入れる． 軸を中央でとる場合，最初からある程度昇順または逆順のデータに対して，ほぼ半分ずつに分割できる．

クイック・ソート クイック・ソートが最も速くなるケースとは，分割によりデータが毎回ちょうど半分ずつに分かれる場合である． 2分探索での議論から，n 個のデータがちょうど半分ずつに分かれれば，分割の段数は log2n 段になる． 各段階のデータ総数は n, n 個のデータの分割：O(n)  クイック・ソートが 　 うまくいくと O(n log n) n 個 1 段目 2 段目 log2n 段目

クイック・ソート 一方，クイック・ソートにおいて最悪なのは，軸として選んだ値が毎回最小値または最大値の場合である． この場合，分割は 1個と残り全部 (nー1 個) となり，分割の段数は nー1 段．計算量は O(n2) となってしまう． でも平均的には O(nlogn) である. 重要なのは平均計算量．(平均計算量の導出はちょっと難しいので範囲外)． 安定性については，不安定． 30 40 20 50 10 10 30 40 20 20 30 50 10 10 50 40 20 i i i i j j i j j  20 と 20 が入れ替わってしまった

クイック・ソート 最悪のケースを想定すれば O(n2) となってしまうクイック・ソートではあるが，実用上は最速である． 5万個の整数値ソート時間 手法 ランダム 昇順　　 降順　　 直接選択法 15.82 15.80 22.11 バブル・ソート 40.09 21.75 43.46 シェーカー・ソート 24.40 0.00 35.14 基本挿入法 13.11 32.91 シェル・ソート 0.09 0.06 ヒープ・ソート (第6章) 0.05 0.03 クイック・ソート 0.02 0.01

クイック・ソート 最悪のケースを想定すれば O(n2) となってしまうクイック・ソートではあるが，実用上は最速である． 500万個の整数値ソート時間 手法 ランダム 昇順　　 降順　　 シェーカー・ソート 問題外 0.10 基本挿入法 0.17 シェル・ソート 21.42 14.66 16.27 ヒープ・ソート (第6章) 15.58 4.11 4.36 クイック・ソート 3.48 2.19 2.25 出展：林 晴比古，"C言語による実用アルゴリズム入門」， 　　　ソフトバンクパブリッシング

ではクイックソート万歳！でよいか？ 実際に研究室や企業でプログラムを組む場合，扱うデータ量が比較的少なく，ソートの起こる回数が少ない場合も 多い． このようなとき，クイック・ソートはプログラムも複雑，スタックも必要，関数呼び出しオーバーヘッドも発生， といった問題から，避けた方がよい場合もある． 実務をやっている人々の話とかを聞くと，問題によってはバブル・ソート等で済ましてしまうことも多いとか． このあたりの判断は経験の中で勘所を会得していく．

クイック・ソート (ソースコード) p.208 は，軸を左端とする場合のコード． ソート対象数列は配列 a[]．ソートを実行する実体は関数 void quick(int a[],int left,int right) 引数として a[] を渡すことによって，配列 a[] の先頭ポインタを渡している．第2, 第3引数はソート対象領域． ①で軸 s を設定し，i と j を初期化した後 while(1)のループに入る．つまり，break するまで繰り返す． 内部の1つめの while ループは，i に 1 を足してから a[i] と s を比較し，a[i] < s である間は繰り返す． while(a[++i]<s) なら 1 を足すのが先，while(a[i++]<s) なら 比較が先 となることに注意． あとは，既に見たアルゴリズム通りである．

4-3 順列の生成 n個の数字を使ってできる順列をすべて求める． n個の数字で順列を作る問題は，先頭の数字 (1, 2, …, n) ごとに，残り n-1 個の数字から順列を作る問題に帰着できる．更に，n-1 個の順列問題は n-2 個の順列問題に帰着できる  再帰的問題として解ける． 先頭の数字に 1～n を持ってくるには，数列の第 1 項と，第 1 項から第 n 項を一つ一つ交換する．1回交換するごとに，残りの n-1個の数字について同じ処理をするために，再帰呼出を行う． この再帰呼出処理が終わったら，入れ替えた数字を元に戻し，別の項との入れ替えを行って，再び再帰呼出を行う．これを繰り返せばよい．

4-3 順列の生成 例えば 1, 2, 3, 4 についての例では， 1, 2, 3, 4 の順列を求める問題 ＝ 1 と 1 を交換した 1234 のうち，2, 3, 4 の順列を求める問題 ＋ 1 と 2 を交換した 2134 のうち，1, 3, 4 の順列を求める問題 ＋ 1 と 3 を交換した 3214 のうち，2, 1, 4 の順列を求める問題 ＋ 1 と 4 を交換した 4231 のうち，2, 3, 1 の順列を求める問題 のように分解できる．更に，残り3つの数の順列問題も， 3通りの先頭数字それぞれに対する2数の順列問題になる．

4-3 順列の生成 数字同士の交換の基点 i は，再帰呼出が深くなるたびに1つずつ進めていく． 1234の順列を求める関数を呼び出す 1234の1番目の位置 1を1番目以降の位置と交換 まずは1と交換して1234 234の順列を求める関数を呼び出す 1234の2番目の位置 2を2番目以降の位置と交換 まずは2と交換して1234 34の順列を求める関数を呼び出す 1234の3番目の位置 3を3番目以降の位置と交換 …

4-3 順列の生成 1 2 3 4 1 2 3 4 終了条件：i==4 1 2 4 3 i=3 1 3 2 4 1 2 3 4 1 3 2 4 1 3 4 2 i=2 1 4 3 2 1 4 3 2 2 1 3 4 1 4 2 3 1 2 3 4 i=1 3 2 1 4 4 2 3 1

4-3 順列の生成 (ソースコード) 注意点：おそらく説明の分かりやすさを目的としてか, ここでは数字の位置の番号付けを 0 番からではなく 1 番から始めている点に注意．従って，N 個の数字を収める配列 p[] のサイズが N+1 になっている． 順列を求める再帰的関数は void perm(int i)． 数字の交換を行う位置 i が N 未満の時は，i 番目の数を i 番目以降の位置 j と順番に交換し，それぞれに対して perm(i-1) を再帰呼出したあと，入れ替えた順番を元に戻してから，関数を抜ける． 終了条件として，i == N に達したら，できた順列を画面に表示して関数を抜ける． 配列 p[N+1] はグローバル変数 (好ましくはない)．

辞書順式に順列生成 p.183 の図4.8を見ると分かるとおり，先程の例では，数字が辞書式順 (昇順) に生成されない． 例えば 1234 の1文字目を決める手順に関して，交換による方法では 1234, 2134, 3214, 4231 となった． ローテーションによる方法では，1234，2134，3124, 4123 となる．