JavaScript再帰関数の実例

概要: このチュートリアルでは、再帰という技法を使用して、自分自身を呼び出す関数であるJavaScript再帰関数を開発する方法を学びます。

JavaScript再帰関数の紹介

再帰関数とは、自身を呼び出す関数であり、呼び出しを停止する条件が満たされるまで繰り返されます。この技法は再帰と呼ばれます。

recurse()という関数があるとします。recurse()は、以下のように、その本体内で自身を呼び出す場合、再帰関数です。

function recurse() {
    // ...
    recurse();
    // ...
}
Code language: JavaScript (javascript)

再帰関数には、常に自身を呼び出すのを停止するための条件があります。そうでなければ、無限に自身を呼び出し続けます。そのため、再帰関数は通常、次のようになります。

function recurse() {
    if(condition) {
        // stop calling itself
        //...
    } else {
        recurse();
    }
}Code language: JavaScript (javascript)

一般的に、再帰関数は、大きな問題を小さな問題に分割するために使用されます。典型的には、二分木やグラフなどのデータ構造、および二分探索やクイックソートなどのアルゴリズムで再帰関数が見られます。

JavaScript再帰関数の例

再帰関数の使用例をいくつか見てみましょう。

1) シンプルなJavaScript再帰関数の例

指定された数値から1までカウントダウンする関数を開発する必要があるとします。たとえば、3から1までカウントダウンするには、

3
2
1

countDown()関数を以下に示します。

function countDown(fromNumber) {
    console.log(fromNumber);
}

countDown(3);Code language: JavaScript (javascript)

このcountDown(3)は、数字の3のみを表示します。

数字の3から1までカウントダウンするには、

数字の3を表示します。
そして、数字の2を表示するcountDown(2)を呼び出します。
そして、数字の1を表示するcountDown(1)を呼び出します。

以下は、countDown()を再帰関数に変更したものです。

function countDown(fromNumber) {
    console.log(fromNumber);
    countDown(fromNumber-1);
}

countDown(3);Code language: JavaScript (javascript)

このcountDown(3)は、コールスタックサイズを超えるまで実行され、次のようになります。

Uncaught RangeError: Maximum call stack size exceeded.Code language: JavaScript (javascript)

…なぜなら、自身を呼び出すのを停止するための条件がないからです。

カウントダウンは、次の数値がゼロになったときに停止します。したがって、以下のようにif条件を追加します。

function countDown(fromNumber) {
    console.log(fromNumber);

    let nextNumber = fromNumber - 1;

    if (nextNumber > 0) {
        countDown(nextNumber);
    }
}
countDown(3);Code language: JavaScript (javascript)

出力

3
2
1

countDown()は期待どおりに動作しているようです。

しかし、関数型チュートリアルで述べたように、関数の名前は実際の関数オブジェクトへの参照です。

コードのどこかで関数名がnullに設定されている場合、再帰関数は動作を停止します。

たとえば、次のコードはエラーになります。

let newYearCountDown = countDown;
// somewhere in the code
countDown = null;
// the following function call will cause an error
newYearCountDown(10);Code language: JavaScript (javascript)

エラー

Uncaught TypeError: countDown is not a functionCode language: JavaScript (javascript)

スクリプトの仕組み

まず、countDown関数名を変数newYearCountDownに代入します。
次に、countDown関数参照をnullに設定します。
3番目に、newYearCountDown関数を呼び出します。

このコードは、countDown()関数の本体が、関数呼び出し時にnullに設定されていたcountDown関数名を参照しているため、エラーが発生します。

これを修正するには、次のように名前付き関数式を使用できます。

let countDown = function f(fromNumber) {
    console.log(fromNumber);

    let nextNumber = fromNumber - 1;

    if (nextNumber > 0) {
        f(nextNumber);
    }
}

let newYearCountDown = countDown;
countDown = null;
newYearCountDown(10);Code language: JavaScript (javascript)

2) n個の自然数の和を計算する例

再帰技法を使用して、1からnまでの自然数の和を計算する必要があるとします。そのためには、次のようにsum()を再帰的に定義する必要があります。

sum(n) = n + sum(n-1)
sum(n-1) = n - 1 + sum(n-2)
...
sum(1) = 1

以下は、sum()再帰関数を示しています。

function sum(n) {
  if (n <= 1) {
    return n;
  }
  return n + sum(n - 1);
}Code language: JavaScript (javascript)

ベースケース

関数は、nが1以下かどうかをチェックする「if」文で始まります。
nが1以下の場合、関数は単にnを返します。これはベースケースであり、再帰の停止条件として機能します。

再帰ケース

ベースケースが満たされない場合（つまり、nが1より大きい場合）、関数は「if」文の後のブロックに入ります。
関数は、nと、引数(n - 1)で自身を呼び出した結果の和を返します。ここで再帰が発生します。

仕組み

たとえば、sum(3)を呼び出すと、関数は最初に3が1以下かどうかをチェックします（ベースケースは満たされません）。
ベースケースではないため、3 + sum(2)を計算します。ここで、引数2で自身を呼び出します。
sum(2)を使用した次の再帰呼び出しでは、2 + sum(1)を計算します。
再び、sum(1)を使用した次の再帰呼び出しでは、ベースケースに達し、1を返します。
これで、前の呼び出しが解決されます。2 + 1は3になり、3 + 3は最終結果の6になります。

終了

再帰は、ベースケースに達するまで、問題をより小さな部分問題に縮小し続けます。
ベースケースに達すると、関数は巻き戻しを開始し、各レベルの再帰の結果を組み合わせて最終結果を取得します。

まとめ

再帰関数とは、停止条件が満たされるまで自身を呼び出す関数のことです。
再帰関数には、常に自身を呼び出すのを停止するための条件があります。

このチュートリアルは役に立ちましたか？