再帰さいきの基本きほん

1導入どうにゅう

この講義こうぎでは、再帰算法さいきさんぽうを、同種どうしゅの小ちいさい入力にゅうりょくに対たいする結果けっかから元もとの入力にゅうりょくに対たいする結果けっかを構成こうせいする方法ほうほうとして説明せつめいする。設計せっけいに必要ひつような基底条件きていじょうけん、再帰段階さいきだんかい、停止尺度ていししゃくどを定義ていぎし、停止性ていしせいと正当性せいとうせいを区別くべつして証明しょうめいする。さらに、呼出よびだしスタックによる実行過程じっこうかていと計算量けいさんりょうを解説かいせつする。

2再帰算法さいきさんぽうの構成要素こうせいようそ

再帰算法さいきさんぽうRecursive algorithmとは、ある入力にゅうりょくに対たいする計算けいさんの途中とちゅうで、同一どういつの算法さんぽうを別べつの入力にゅうりょくに適用てきようする算法さんぽうである。この適用てきようを再帰呼出さいきよびだしRecursive callという。

基底条件きていじょうけんBase caseとは、再帰呼出さいきよびだしを実行じっこうせずに結果けっかを直接返ちょくせつかえす条件じょうけんである。再帰段階さいきだんかいRecursive stepとは、基底条件きていじょうけんを満みたさない入力にゅうりょくを小ちいさい同種どうしゅの入力にゅうりょくへ変換へんかんし、その再帰呼出さいきよびだしの結果けっかから元もとの結果けっかを構成こうせいする規則きそくである。

停止尺度ていししゃくどTermination measureとは、各入力かくにゅうりょくに非負整数ひふせいすうを対応たいおうさせ、各再帰呼出かくさいきよびだしで厳密げんみつに減少げんしょうする量りょうである。この量りょうは再帰呼出さいきよびだしが無限むげんに継続けいぞくしないことを証明しょうめいするために使用しようする。

3階乗かいじょうの再帰的定義さいきてきていぎ

$$n\in Z_{\ge 0}$$n\in\mathbb{Z}_{\geq 0} に対たいする階乗かいじょうを次つぎで定義ていぎする。

関数かんすう $$\mathrm{fact}\left(n\right)$$\operatorname{fact}(n) の仕様しようを「$$n\in Z_{\ge 0}$$n\in\mathbb{Z}_{\geq0} を受うけ取とり、$$n!$$n! を返かえす」とする。この仕様しように対たいする再帰算法さいきさんぽうは次つぎのように記述きじゅつできる。

fact(n):
    if n = 0:
        return 1
    return n * fact(n - 1)

$$n=0$$n=0 が基底条件きていじょうけんであり、$$n\ge 1$$n\geq1 における $$n\mathrm{fact}(n-1)$$n\operatorname{fact}(n-1) の計算けいさんが再帰段階さいきだんかいである。停止尺度ていししゃくどには $$\mu \left(n\right)=n$$\mu(n)=n を採用さいようする。

4停止性ていしせい

$$n=0$$n=0 なら再帰呼出さいきよびだしを実行じっこうせずに終了しゅうりょうする。$$n\ge 1$$n\geq1 なら、再帰呼出さいきよびだしの入力にゅうりょくは $$n-1$$n-1 であり、

が成立せいりつする。したがって、非負整数ひふせいすうである停止尺度ていししゃくどは各再帰呼出かくさいきよびだしで厳密げんみつに減少げんしょうする。非負整数ひふせいすうの厳密減少列げんみつげんしょうれつは無限むげんに継続けいぞくしないため、有限回ゆうげんかいの呼出よびだしの後あとに $$n=0$$n=0 へ到達とうたつする。よって $$\mathrm{fact}\left(n\right)$$\operatorname{fact}(n) はすべての $$n\in Z_{\ge 0}$$n\in\mathbb{Z}_{\geq0} で停止ていしする。

5正当性せいとうせい

停止性ていしせいは「計算けいさんが終了しゅうりょうする」ことを保証ほしょうするが、「返値かえりちが仕様しようを満みたす」ことは別べつに証明しょうめいする必要ひつようがある。$$n$$n に関かんする数学的帰納法すうがくてききのうほうを用もちいる。

• 基底段階きていだんかい：$$n=0$$n=0 では、算法さんぽうは $$1$$1 を返かえす。$$0!=1$$0!=1 であるため、返値かえりちは正ただしい。
• 帰納段階きのうだんかい：$$n\ge 1$$n\geq1 とし、$$\mathrm{fact}(n-1)=(n-1)!$$\operatorname{fact}(n-1)=(n-1)! を帰納法きのうほうの仮定かていとする。算法さんぽうの返値かえりちは $$n\mathrm{fact}(n-1)$$n\operatorname{fact}(n-1) であるから、仮定かていと階乗かいじょうの定義ていぎにより

となる。

したがって、すべての $$n\in Z_{\ge 0}$$n\in\mathbb{Z}_{\geq0} について $$\mathrm{fact}\left(n\right)=n!$$\operatorname{fact}(n)=n! が成立せいりつする。基底条件きていじょうけんと再帰段階さいきだんかいは、それぞれ帰納法きのうほうの基底段階きていだんかいと帰納段階きのうだんかいに対応たいおうする。

6呼出よびだしスタック

呼出よびだしフレームStack frameとは、一回いっかいの関数呼出かんすうよびだしに必要ひつような引数ひきすう、局所変数きょくしょへんすう、復帰位置ふっきいちなどを保持ほじする記録きろくである。呼出よびだしスタックCall stackとは、未完了みかんりょうの呼出よびだしフレームを後入先出あといれさきだしの順序じゅんじょで保持ほじするスタックである。

$$\mathrm{fact}\left(3\right)$$\operatorname{fact}(3) の実行じっこうでは、$$\mathrm{fact}\left(3\right)$$\operatorname{fact}(3)、$$\mathrm{fact}\left(2\right)$$\operatorname{fact}(2)、$$\mathrm{fact}\left(1\right)$$\operatorname{fact}(1)、$$\mathrm{fact}\left(0\right)$$\operatorname{fact}(0) の順じゅんにフレームが積つまれる。基底条件きていじょうけんが $$1$$1 を返かえした後あと、逆順ぎゃくじゅんに復帰ふっきして $$1$$1、$$2$$2、$$6$$6 を構成こうせいする。したがって、再帰呼出さいきよびだしの深ふかさは同時どうじに保持ほじするフレーム数すうを決定けっていする。

7計算量けいさんりょう

ここでは、各算術演算かくさんじゅつえんざんの費用ひようを $$\mathrm{\Theta }\left(1\right)$$\Theta(1) とする単位費用たんいひよう RAM モデルUnit-cost RAM modelを採用さいようし、算術演算回数さんじゅつえんざんかいすうを評価ひょうかする。任意精度整数にんいせいどせいすうのビット演算量えんざんりょうを評価ひょうかする場合ばあい、$$n!$$n! の桁数けたすうと乗算算法じょうざんさんぽうの費用ひようを別途考慮べっとこうりょする必要ひつようがある。

このモデルでは、$$\mathrm{fact}\left(n\right)$$\operatorname{fact}(n) は $$n>0$$n>0 の各入力かくにゅうりょくについて一回いっかいの再帰呼出さいきよびだしと定数時間ていすうじかんの乗算じょうざんを実行じっこうする。時間計算量じかんけいさんりょう $$T\left(n\right)$$T(n) は

を満みたすため、$$T\left(n\right)=\mathrm{\Theta }\left(n\right)$$T(n)=\Theta(n) である。最大さいだいの呼出深度よびだししんどは $$n+1$$n+1 であり、各かくフレームが定数量ていすうりょうの領域りょういきを使用しようするため、呼出よびだしスタックの補助空間計算量ほじょくうかんけいさんりょうは $$\mathrm{\Theta }\left(n\right)$$\Theta(n) である。

8設計せっけいと検証けんしょうの手順てじゅん

1. 入力にゅうりょくと返値かえりちの仕様しようを明示めいじする。
2. 再帰呼出さいきよびだしを要ようしない基底条件きていじょうけんを定さだめる。
3. 小ちいさい同種どうしゅの入力にゅうりょくから結果けっかを構成こうせいする再帰段階さいきだんかいを定さだめる。
4. 各再帰呼出かくさいきよびだしで厳密げんみつに減少げんしょうする停止尺度ていししゃくどを提示ていじし、停止性ていしせいを証明しょうめいする。
5. 帰納法きのうほうなどにより正当性せいとうせいを証明しょうめいする。
6. 再帰呼出さいきよびだしの回数かいすうと最大深度さいだいしんどから時間じかん・空間計算量くうかんけいさんりょうを評価ひょうかする。