第一章ガイドライン

再帰簡論
ほとんどの数学式はもう一つの簡単な関数で記述されています.例:
C=5(F-32)/9温度変換
しかし、時々このような状況があります.
F(0)=0を満たし、F(X)=2 F(X-1)+X^2を満たす関数Fを定義します.
この関数をそれ自身で定義するときは再帰(recursive)と呼ばれ,次のコードはFの再帰実装を示す.

int F(int X)
{
    if (X == 0)                         
        return 0;
    else
        return 2 *F(X - 1) + X * X;
}

F(4)を計算すると、実際にはF(3)+4を計算するとします.×4,このようにF(3)を呼び出す必要があり、F(3)を計算する際にF(2)を呼び出す必要があり、F(0)=0になるまで呼び出す.
再帰呼び出しは、基準シナリオが現れるまで繰り返されることに注意してください.例えば、F(-1)の値を計算すると、F(-2)、F(-3)などが呼び出され、この場合、基準シナリオが発生することはあり得ないため、システムは答えを算出できない.
再帰関数のもう1つの注意すべき問題は、計算を定義できないことです.たとえば、次のようにします.

int BAD(int X)
{
    if (X == 0)                         
        return 0;
    else
        return BAD（X / 3 + 1) + X - 1;
}

このエラーは、BAD(1)をBAD(1)と定義し、コンピュータがBAD(1)を繰り返し呼び出し、計算できなくなることです.再帰には2つの基本法則が必要です

基準シナリオ(base case):再帰せずに解くことができるいくつかの基準シナリオが重要でなければなりません.

継続推進(making progress):再帰的に解く必要がある場合、再帰的呼び出しは、基準シナリオを生成する方向に推進されなければならない.

設計法則(design rule):再帰プログラムを設計するときに管理の詳細を知る必要はなく、大量の再帰呼び出しを追跡しようとする必要はありません.

合成利益法則(compound interest rule):後で説明します.

まとめ
1章で残りの部分のために舞台を建てた.大量の入力に直面するアルゴリズムに対して,彼が費やした時間はその良し悪しを判別する重要な基準であり,次の章でこれらの問題について述べる.ここで論じた数学概念を用いて正式なモデルを構築する.