再帰
更新 : 2007 年 11 月
再帰は、関数で関数自身を呼び出す、重要なプログラミング手法です。再帰法を使用した簡単な例として、階乗の計算があります。0 の階乗は明確に 1 であると定義されます。n を 0 より大きい整数とすると、n の階乗は 1 ～ n の範囲にある整数すべての積になります。
再帰の使用
次の段落は、階乗を求める関数の定義です。
"指定された数字が 0 より小さい場合は、計算しません。整数以外は計算しません。階乗を求める数字が 0 の場合、階乗は 1 です。階乗を求める数字が 1 以上の場合は、その数字にその数字より 1 だけ小さい値の階乗を掛けます。"
0 より大きい数値の階乗を計算する場合、他の数値の階乗を少なくとも 1 つ計算する必要があります。関数を現在の数値に対して実行する前に、1 つ小さい数値に対して自身を呼び出す必要があります。これが、再帰の一例です。
再帰と反復計算 (ループ) には強い関連があります。再帰と反復計算のどちらでも、関数は同じ結果を返すことができます。通常、どちらの処理方法が適しているかは、実行する計算によって決まります。プログラマは、その計算に対して最も無理のない方法、または最も適した方法を選択するだけです。
再帰は便利ですが、結果を返さず、終了しない再帰関数を簡単に作成してしまう可能性があります。このような再帰は "無限" ループになります。たとえば、階乗の計算の定義から最初の規則 (負の値に関する規則) を省略して関数を作成し、この関数を使用して負の値の階乗を求めようとしたとします。この場合、たとえば -24 の階乗を計算しようとすると、-25 の階乗の計算が必要となります。-25 の階乗を計算するためには、さらに -26 の階乗の計算が必要となります。このように処理が行われていくと、再帰呼び出しは終了しません。
再帰で発生する別の問題は、再帰関数が利用可能なリソース (システム メモリ、スタック領域など) をすべて使用してしまう可能性があることです。再帰関数が自身を (または、元の関数を呼び出す別の関数を) 呼び出すごとに、いくらかのリソースが使用されます。これらのリソースは再帰関数が終了するときに解放されますが、再帰のレベルが多すぎる関数は、利用可能なすべてのリソースを使用する可能性があります。利用可能なリソースがすべて使用されると、例外がスローされます。
このように、再帰関数は注意してデザインする必要があります。再帰が過度に (または無限に) なる可能性がある場合は、自身を呼び出した回数をカウントし、呼び出し回数を制限するように関数をデザインします。関数が自身を呼び出した回数がしきい値を超えたら、関数を自動的に終了します。最適となる最大の反復処理回数は、再帰関数によって異なります。
次に、階乗を求める関数の定義を JScript のコードで示します。型の注釈を指定して、関数が整数だけを受け取るようにします。無効な数値 (0 より小さい数) が渡された場合は、throw ステートメントがエラーを生成します。それ以外の場合は、再帰関数を使用して階乗を計算します。再帰関数は 2 つの引数を受け取ります。1 つは階乗の引数で、もう 1 つは現在の再帰レベルを追跡するためのカウンタです。カウンタが最大の再帰レベルに達しなかった場合は、元の数の階乗が返されます。
function factorialWork(aNumber : int, recursNumber : int ) : double {
// recursNumber keeps track of the number of iterations so far.
if (aNumber == 0) { // If the number is 0, its factorial is 1.
return 1.;
} else {
if(recursNumber > 100) {
throw("Too many levels of recursion.");
} else { // Otherwise, recurse again.
return (aNumber * factorialWork(aNumber - 1, recursNumber + 1));
}
}
}
function factorial(aNumber : int) : double {
// Use type annotation to only accept numbers coercible to integers.
// double is used for the return type to allow very large numbers to be returned.
if(aNumber < 0) {
throw("Cannot take the factorial of a negative number.");
} else { // Call the recursive function.
return factorialWork(aNumber, 0);
}
}
// Call the factorial function for two values.
print(factorial(5));
print(factorial(80));
このプログラムの出力は次のようになります。
120
7.156945704626378e+118