再帰法

再帰法は、重要なプログラミング手法です。再帰法では、関数がその関数自身を呼び出します。再帰法を使用した簡単な例として、階乗の計算があります。0 の階乗は、共に 1 になります。これより大きい数の階乗は、1 * 2 * ... というように階乗を求める数になるまで数字を 1 ずつ増やしながら掛けていくことにより算出できます。

次の段落は、階乗を求める関数の定義です。

"指定された数字が 0 より小さい場合は、計算しません。また、整数でない場合は、端数を切り捨てて整数にします。階乗を求める数字が 0 の場合は、階乗は 1 です。階乗を求める数字が 1 以上の場合は、その数字にその数字より 1 だけ小さい値の階乗を掛けます。"

この計算を行うために使用する関数は、既に作成している関数です。つまり、この関数は、自分自身を呼び出して 1 つ小さい数の階乗を求めることにより、目的の数の階乗を計算できるようになります。これが、再帰の一例です。

再帰法とループの反復処理は密接な関係があります。再帰により反復処理が実行され、反復処理を実行すると再帰が起こります。通常、特定の処理によりその処理自身がある手法に引き渡されるため、ユーザーは単に使いやすい手法を選択するだけで済みます。

しかし、注意しなければならない点があります。再帰法を使用すると、再帰呼び出しが終了しないで永久に結果を得られない再帰関数を作成してしまうことがよくあります。このような再帰は、いわゆる "無限" ループになります。たとえば、階乗の計算の定義から最初の規則 (負の値に関する規則) を省略して関数を作成し、この関数を使用して負の値の階乗を求めようとしたとします。-24 の階乗を求めようとした場合なら、まず -25 の階乗を求めることになります。すると、次に -26 の階乗を求めることになります。このように処理が行われていくと、明らかに再帰呼び出しが終了しないことになります。このため、関数の実行は正常に終了しません。

したがって、再帰関数は、特に注意して設計する必要があります。無限再帰になる可能性がないと思われる場合でも、関数内で再帰呼び出しの回数をカウントしておけば、呼び出しの回数が非常に多くなってあらかじめ設定しておいた回数を超えたときには自動的に実行が終了するように設計することもできます。

次に、階乗を求める関数の定義を、JScript のコードで示します。

// 階乗を計算する関数です。不正な値
// (0 より小さい値) が渡された場合、-1 
// が返され、エラーであることを知らせます。
// それ以外の場合は、数値は最も近い整数に変換され、
// その階乗が返されます。
function factorial(aNumber)  {
aNumber = Math.floor(aNumber);  // 数値が整数でない場合は、端数を切り捨てます。
if (aNumber < 0)  {  // 数値が 0 より小さい場合は、計算を中止します。
    return -1;
    }
if (aNumber == 0)  {  // 数値が 0 場合は、その階乗は 1 です。
      return 1;
      }
else return (aNumber * factorial(anumber - 1));  // それ以外の場合は、数値が 1 になるまで再帰呼び出しを行います。
}
表示: