再帰さいきの基本きほん

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. 再帰呼出さいきよびだしの回数かいすうと最大深度さいだいしんどから時間じかん・空間計算量くうかんけいさんりょうを評価ひょうかする。

Recursion Basics

1Introduction

This lecture explains a recursive algorithm as a method that constructs the result for an input from the result for a smaller input of the same kind. It defines the base case, recursive step, and termination measure needed for the design, and proves termination and correctness separately. It also explains the execution process through the call stack and analyzes its complexity.

2Components of a Recursive Algorithm

A recursive algorithmRecursive algorithm is an algorithm that applies itself to another input during a computation. Such an application is a recursive callRecursive call.

A base caseBase case is a condition under which the algorithm returns a result directly without making a recursive call. A recursive stepRecursive step transforms an input that does not satisfy a base case into a smaller input of the same kind and constructs the original result from the result of the recursive call.

A termination measureTermination measure assigns a nonnegative integer to every input and strictly decreases in every recursive call. It is used to prove that recursive calls cannot continue indefinitely.

3Recursive Definition of Factorial

For $$n\in Z_{\ge 0}$$n\in\mathbb{Z}_{\geq0}, factorial is defined by

The specification of $$\mathrm{fact}\left(n\right)$$\operatorname{fact}(n) is: given $$n\in Z_{\ge 0}$$n\in\mathbb{Z}_{\geq0}, return $$n!$$n!. A recursive algorithm satisfying this specification is

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

The condition $$n=0$$n=0 is the base case, and the computation of $$n\mathrm{fact}(n-1)$$n\operatorname{fact}(n-1) for $$n\ge 1$$n\geq1 is the recursive step. We choose $$\mu \left(n\right)=n$$\mu(n)=n as the termination measure.

4Termination

If $$n=0$$n=0, the algorithm terminates without a recursive call. If $$n\ge 1$$n\geq1, the recursive call receives $$n-1$$n-1, and

Thus, the nonnegative-integer termination measure strictly decreases in every recursive call. A strictly decreasing sequence of nonnegative integers cannot be infinite, so the computation reaches $$n=0$$n=0 after finitely many calls. Therefore, $$\mathrm{fact}\left(n\right)$$\operatorname{fact}(n) terminates for every $$n\in Z_{\ge 0}$$n\in\mathbb{Z}_{\geq0}.

5Correctness

Termination guarantees that the computation ends, but it does not by itself guarantee that the return value satisfies the specification. We prove the latter claim by induction on $$n$$n.

• Base case: for $$n=0$$n=0, the algorithm returns $$1$$1. Since $$0!=1$$0!=1, the return value is correct.
• Inductive step: let $$n\ge 1$$n\geq1 and assume $$\mathrm{fact}(n-1)=(n-1)!$$\operatorname{fact}(n-1)=(n-1)!. The algorithm returns $$n\mathrm{fact}(n-1)$$n\operatorname{fact}(n-1). By the inductive hypothesis and the definition of factorial,

Therefore, $$\mathrm{fact}\left(n\right)=n!$$\operatorname{fact}(n)=n! for every $$n\in Z_{\ge 0}$$n\in\mathbb{Z}_{\geq0}. The base case and recursive step correspond respectively to the base case and inductive step of the proof.

6Call Stack

A stack frameStack frame is a record containing the arguments, local variables, return location, and other information required by one function call. The call stackCall stack stores the stack frames of unfinished calls in last-in, first-out order.

During the evaluation of $$\mathrm{fact}\left(3\right)$$\operatorname{fact}(3), frames for $$\mathrm{fact}\left(3\right)$$\operatorname{fact}(3), $$\mathrm{fact}\left(2\right)$$\operatorname{fact}(2), $$\mathrm{fact}\left(1\right)$$\operatorname{fact}(1), and $$\mathrm{fact}\left(0\right)$$\operatorname{fact}(0) are pushed in that order. After the base case returns $$1$$1, the calls return in reverse order and construct $$1$$1, $$2$$2, and $$6$$6. Consequently, the recursive-call depth determines the number of frames stored simultaneously.

7Complexity

We use the unit-cost RAM modelUnit-cost RAM model, in which every arithmetic operation costs $$\mathrm{\Theta }\left(1\right)$$\Theta(1), and count arithmetic operations. An analysis of arbitrary-precision bit complexity must instead account for the number of bits in $$n!$$n! and the cost of the multiplication algorithm.

In this model, for each input with $$n>0$$n>0, $$\mathrm{fact}\left(n\right)$$\operatorname{fact}(n) makes one recursive call and performs a constant-time multiplication. Its time complexity satisfies

so $$T\left(n\right)=\mathrm{\Theta }\left(n\right)$$T(n)=\Theta(n). The maximum call depth is $$n+1$$n+1. Because each frame uses a constant amount of storage, the auxiliary-space complexity of the call stack is $$\mathrm{\Theta }\left(n\right)$$\Theta(n).

8Design and Verification Procedure

1. State the specification of the input and return value.
2. Define a base case that requires no recursive call.
3. Define a recursive step that constructs the result from a smaller input of the same kind.
4. Provide a termination measure that strictly decreases in every recursive call, and prove termination.
5. Prove correctness, for example by induction.
6. Evaluate time and space complexity from the number of recursive calls and the maximum call depth.