「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

みなさんは「合わせ鏡」を知っていますか？
2枚の鏡（A、B）を向い合せに置いたときに起きる現象で、鏡Aの中に鏡Bが写り、鏡Aに写っている鏡Bの中に鏡Aが写り、鏡Aに写っている鏡Bの中に写っている鏡Aの中に鏡Bが写り……と、無限に入れ子になる現象です。



それを踏まえて

自分自身を呼び出す処理が書かれている関数を呼び出す

のが「再帰呼出し」です。



対象が関数ではなく、プログラムの部品だったり他の何かだったりする場合もあるかもしれません。
そこら辺は、ゆるく解釈してください。

とにかく

自分自身を呼び出す処理が書かれている何か

を呼び出すことです。

それでは次に実際の例を見てみましょう。

例えば、そうですね。
以下の処理をやるピヨ太関数が ありました。

１．ミカン箱を受け取る

２．ミカンを1個食べる

３．ミカンが残っていたら、ピヨ太関数（自分自身）を呼び出してミカン箱を渡す

４．ミカンがなくなったら、終わり

ピヨ太関数はミカン箱を受け取ります。



ピヨ太関数はミカンを1個食べます。



ミカン箱にミカンが残っていたら、再度、ピヨ太関数を呼び出します。
このとき、残りのミカンが入ったミカン箱を渡します。



分かりにくいので、ピヨ太関数から呼び出されたピヨ太関数は「ピヨ太関数2号」と呼びますね。
ピヨ太関数2号は、呼び出し元のピヨ太関数からミカン箱を受け取ります。



ピヨ太関数2号はミカンを1個食べます。



ミカン箱にミカンが残っていたら、再度、ピヨ太関数を呼び出します。
このとき、残りのミカンが入ったミカン箱を渡します。



ピヨ太関数2号から呼び出されたピヨ太関数は「ピヨ太関数3号」と呼びますね。
ピヨ太関数3号は、呼び出し元のピヨ太関数2号からミカン箱を受け取ります。



ピヨ太関数3号はミカンを1個食べます。



おっと、ミカン箱が空っぽになりました。
これで処理は終了です。



今回はピヨ太関数が3号まで登場しました。
これはミカン箱にミカンが3個入っていたからです。



もしミカン箱に入っているミカンが4個なら、ピヨ太関数は4号まで登場します。
5個なら5号、6個なら6号、10個なら10号まで登場するでしょう。



このように

自分自身を呼び出す処理が書かれている何かを呼び出す

のが再帰呼出しです。

せっかくなので、もう少しプログラムっぽい例も書いておきましょう。
PHPで書いたサンプルですが、以下の処理は再帰呼出しになっています。

<?php

//-------------------------------
//ピヨ太関数
//-------------------------------
function piyota($mikan = 0){

    // ミカンを食べる
    $mikan = $mikan - 1;

    // 残りミカン数を表示
    print "残りミカン数：" . $mikan . "\n";

    if($mikan > 0){    //残りミカンあり
        //ピヨ太関数を再帰呼出し
        return piyota($mikan);
    }else{
        //終了
        print "終わり";
        return 0;
    }
}

//-------------------------------
//主処理
//-------------------------------

//最初のミカンの数
$mikan_num = 10;

//ピヨ太関数呼び出し
piyota($mikan_num);

この処理の実行結果は、以下の通りです。

残りミカン数：9
残りミカン数：8
残りミカン数：7
残りミカン数：6
残りミカン数：5
残りミカン数：4
残りミカン数：3
残りミカン数：2
残りミカン数：1
残りミカン数：0
終わり

それっぽく動いていますね。

$mikan_num = 10;

の「10」を変えれば、関数「piyota()」が呼び出される回数も変わります。

再帰呼出しは、上手く使うと「デキるプログラマ」になった気分を味わえます。
「再帰呼出しを使いこなしているオレ、かっけー」となるでしょう。

それが罠です。

再帰呼出しを使うときは、ご注意ください。
再帰呼出しには、少なからずリスクがあります。

他にもあるとは思いますが、私がパッと思い浮かぶリスクは以下の2つです。

１．終了条件が間違っていると処理が終わらなくなる
２．入れ子が深くなると、メモリが足りなくなる

先ほどのピヨ太関数を例に、それぞれ説明しますね。
まずは

１．終了条件が間違っていると処理が終わらなくなる

について説明します。

ピヨ太関数の処理は

１．ミカン箱を受け取る

２．ミカンを1個食べる

３．ミカンが残っていたら、ピヨ太関数（自分自身）を呼び出してミカン箱を渡す

４．ミカンがなくなったら、終わり

でした。
これが、もし

１．ミカン箱を受け取る

２．ミカンを1個舐める

３．ミカンが残っていたら、ピヨ太関数（自分自身）を呼び出してミカン箱を渡す

４．ミカンがなくなったら、終わり

だったら、どうでしょう？

ミカンは食べません。
舐めるだけです。
舐め終わったミカンはミカン箱の中に戻します。

この状態でピヨ太関数を実行すると、ピヨ太関数が無限に増え続けます。
ミカン箱のミカンは絶対になくならないからです。
ひたすらピヨ太関数が呼び出され続けます。



これは大変ですね。
ピヨ太関数が増え続けるだけで、いつまで待っても処理が終わりません。
ピヨ太関数を動かしているコンピュータが力尽きるのが先でしょう。

これが

１．終了条件が間違っていると処理が終わらなくなる

です。
「間違わなければ、いいじゃん！」と言われれば確かにその通りですが、ちょっと心配になりませんか？

次に

２．入れ子が深くなると、メモリが足りなくなる

について説明します。

今度は、ピヨ太関数は正しいピヨ太関数です。
期待通りの処理をしてくれます。

そんなピヨ太関数に、ミカンが100個入ったミカン箱を渡したら、どうなるでしょう？

そうですね。
ピヨ太関数は100号まで登場します。



でも、待ってください。

ピヨ太君のお家は、そんなに広くありません。
100人も入ったら、ピヨ太君が潰れるか、お家の壁が吹っ飛びます。



いずれにせよ、異常事態ですね。

それと同じです。

関数が実行されるとき、メモリが使われます。
再帰呼出しの場合、呼び出される回数が多くなれば、使われるメモリの量も増えます。

メモリは有限です。
呼び出される回数が増えれば、いずれメモリを使い尽くすでしょう。
そうなったら、それで試合終了です。

このように、処理としては何も間違っていないにもかかわらず、動かしたときに変なことになる可能性があります。
呼び出し回数を上手く制御すれば問題ない話ではありますが、ちょっと怖くありませんか？

これが

２．入れ子が深くなると、メモリが足りなくなる

です。

今回説明した2つのリスクは、気を付ければ済む話です。
「問題」と言うほど大げさなものでは ありません。

ですが、リスクはリスクです。

あくまで個人的な意見ですけどね。
再帰呼出しを使わないで済むのであれば、使わないに越したことはないと思います。

あと、再帰呼出しになっている関数は「再帰関数」と言います。
気が向いたら、併せて覚えてあげてください。