小粋空間  -  a cheap joke and a play on words site

プログラムの再帰呼び出しのまとめ

プログラムの再帰呼び出しについてまとめてみました。

ここではJavaScriptを使って説明します。

１．はじめに

プログラムの「再帰呼び出し」とは、関数が実行されたときにその内部から自分自身をさらに呼び出すというテクニックです。

再帰呼び出しは冗長なコードを作り込まないための重要なテクニックですが、ビギナーの方にとっては理解が難しいと思われます。

また、再帰呼び出しについてネットで検索すると多くのページがヒットしますが、個人的に分かりやすいと思ったページがほとんどありませんでした（すいません）。

このエントリーも分かりやすいかどうかわかりませんが、階乗処理（5!=5×4×3×2×1=120）のサンプルを使って再帰呼び出しの流れやポイントなどを説明したいと思います。

２．サンプル

説明で使う再帰呼び出しプログラムのサンプルは下記です。

function recursive(number) {
    if ( number <= 0 ) {
        return 1;
    }
    result = recursive( number - 1 );
    return number * result;
}
result = recursive(5);
console.log( result );

動作は、recursive()という関数のパラメータに「5」を与えて実行すると、

1×2×3×4×5

という計算を行い、120という結果をコンソールに出力します（厳密には1×1→2×1→3×2→6×4→24×5という計算をします）。

ちなみにこのコードは次の4行でも実現できますが、理解を容易にするために冒頭のようにしています。

function recursive( number ) {
    return ( number <= 0 ) ? 1 : ( number * recursive( number - 1 ) );
}
console.log( recursive(5) );

３．解説

プログラムの解説ですが、理解を容易にするためにとりあえず再帰呼び出し関数をすべて別関数にしてみました（かえってわかりにくかったらすいません）。

function recursive1( number ) {
    if ( number <= 0 ) {
        return 1;
    }
    result = recursive2( number - 1 );
    return number * result;
};
function recursive2( number ) {
    if ( number <= 0 ) {
        return 1;
    }
    result = recursive3( number - 1 );
    return number * result;
};
function recursive3( number ) {
    if ( number <= 0 ) {
        return 1;
    }
    result = recursive4( number - 1 );
    return number * result;
};
function recursive4( number ) {
    if ( number <= 0 ) {
        return 1;
    }
    result = recursive5( number - 1 );
    return number * result;
};
function recursive5( number ) {
    if ( number <= 0 ) {
        return 1;
    }
    result = recursive6( number - 1 );
    return number * result;
};
function recursive6( number ) {
    if ( number <= 0 ) {
        return 1;
    }
// サンプルでは以下は動作しません
//  result = recursive6( number - 1 );
//  return number * result;
};
result = recursive(5);
console.log( result );

このプログラムの実行される行と順番は次のとおりです。

recursive1:2  if ( number <= 0 ) { // number = 5
recursive1:5  result = recursive2(number - 1);
recursive2:2  if ( number <= 0 ) { // number = 4
recursive2:5  result = recursive3(number - 1);
recursive3:2  if ( number <= 0 ) { // number = 3
recursive3:5  result = recursive4(number - 1);
recursive4:2  if ( number <= 0 ) { // number = 2
recursive4:5  result = recursive5(number - 1);
recursive5:2  if ( number <= 0 ) { // number = 1
recursive5:5  result = recursive6(number - 1);
recursive6:2  if ( number <= 0 ) { // number = 0
recursive6:3      return 1;
recursive5:6  return number * result; // number = 1 result = 1
recursive4:6  return number * result; // number = 2 result = 2
recursive3:6  return number * result; // number = 3 result = 6
recursive2:6  return number * result; // number = 4 result = 24
recursive1:6  return number * result; // number = 5 result = 120

実行された行でお分かりになったと思いますが、再帰呼び出しプログラムの特徴・ポイントとして、

• 処理を戻す仕組み（ここではnumber<=0の判定でリターン）が必要
• 関数のコード前半（再帰呼び出しの直前）が先に実行される
• 関数のコード後半（再帰呼び出しの直後）が後で実行される

などが挙げられると思います。

冒頭のサンプルプログラムに戻って解説すると、まずパラメータで与えた変数numberが0になるまで再帰呼び出しを繰り返して、赤色の部分を繰り返し処理し、numberをデクリメントします。

function recursive(number) {
    if ( number <= 0 ) {
        return 1;
    }
    result = recursive( number - 1 );
    return number * result;
}
console.log(recursive(5));

最後の再帰呼び出しで変数numberが0になるので1を返却します。階乗処理でこの1の返却が必要になります。

function recursive(number) {
    if ( number <= 0 ) {
        return 1;
    }
    result = recursive( number - 1 );
    return number * result;
}
console.log(recursive(5));

そして、計算と呼び出し元への戻し値の返却が、呼び出された回数分繰り返し行われます。

function recursive(number) {
    if ( number <= 0 ) {
        return 1;
    }
    result = recursive( number - 1 );
    return number * result;
}
console.log(recursive(5));

具体的な計算値と返却値は次のとおりです。

• 1 * 1（1回目のnumber * result）→1を返却
• 1 * 2（2回目のnumber * result）→2を返却
• 2 * 3（3回目のnumber * result）→6を返却
• 6 * 4（4回目のnumber * result）→24を返却
• 24 * 5（5回目のnumber * result）→120を返却

図も作ったので参考になれば幸いです。

（クリックで拡大。拡大後、右下のアイコンクリックで最大化）

４．サンプル2

もう少し分かりやすい例で、HTMLのul/li要素を入れ子で出力するには次のようにします。

function recursive( number ) {
    document.write("<ul><li>"+number);
    if ( number <= 0 ) {
        document.write("</li></ul>");
        return;
    }
    recursive( number - 1 );
    document.write("</li></ul>");
}
recursive(5);

実行すると次のHTMLを出力します。

<ul>
  <li>5
    <ul>
      <li>4
        <ul>
          <li>3
            <ul>
              <li>2
                <ul>
                  <li>1
                    <ul>
                      <li>0</li>
                    </ul>
                  </li>
                </ul>
              </li>
            </ul>
          </li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

以上です。認識誤り等ありましたらどこかでつぶやいてください。