この章からは、しばらく言語の話と言うよりは、アルゴリズムの話になります。その第１回目として、自分自身を呼ぶ関数について話します。

　では、今回の要点です。

　では、いってみましょう。

　唐突ですが、次のプログラムを見て下さい。

// Recurse1.cpp
#include <iostream.h>

void Func()
{
    cout << "forever" << endl;
    Func();
}

int main()
{
    Func();

    return 0;
}

forever
forever
forever
forever
   :
   :
   :
   :
（エラーが出るまで続く）

　何と、Func 関数内で Func 関数を呼びだしています。自分を呼んでいるわけです。確かに、Func の定義内では既に Func の戻り値の型と、引数の情報は分かっています。呼べても不思議はありません。

　このように、自分自身を呼ぶことを再帰呼び出し、そして再帰呼び出ししている関数のことを再帰関数と呼びます。

　しかし、上の結果を見て分かるとおり、Func に入ったが最後関数を抜けることができなくなりました。先ず、Func を呼ぶ。その中で Func が呼ばれ、またその中で Func が呼ばれる。これをずっと続けるわけですから、関数を抜けられないのも当然ですね。

　で、抜けられないままずっと呼び続けているとスタックオーバーフローが起きます（第１部第６１章参照）。実は、どこから呼ばれても呼び出し元へ戻れるようにするために、関数を呼ぶときにスタックへ戻る場所のアドレス（リターンアドレス）を渡します。これがずっと続くので、スタックオーバーフローが起こるわけです。

　ではどうすればいいかといえば、それは特に難しいことではありません。終了条件を付けてやればいいだけです。例えば、こういう風にします。

// Recurse2.cpp
#include <iostream.h>

int i;

void Func()
{
    cout << i << endl;
    i--;
    if(i > 0)
        Func();
}

int main()
{
    i = 5;
    Func();

    return 0;
}

5
4
3
2
1

　グローバル変数 i を作り、それに値を入れておくと、カウントダウンをしていきます。

　先ず、Func が呼ばれます。初めは i は５です。で、cout が 5 が表示されます。

　次に i をデクリメントし、if 文で i が正の時だけ Func を呼ぶようにしてあります。つまり、i が０以下になった時点で Func が呼ばれなくなります。

　すると、i が０以下になったときに、その Func 関数は終了します。そして、呼び出し元の Func 関数も、関数の終わりが来て終了します。このように、堰を切ったように次々と Func 関数が終わっていき、最後に一番初めに Func を呼んだ場所へ戻ります。

　このように、終了条件を入れてやれば再帰関数は簡単に終わらせることができます。

　短いですが、今回はこれで終わりです。これだけでは for 文でいいじゃないかという処理ですね。実用的な話は次回以降に話すことにします。

　では、今回の要点です。

　それでは、次回まで。

第２０章　トークンを結合せよ | 第２２章　call itself ２

Last update was done on 2000.8.23

この講座の著作権はロベールが保有しています