再帰呼び出し | Programming Place Plus　Ｃ言語編　第５３章

このページの概要

以下は目次です。

• 再帰呼び出し
• 関数呼び出しの仕組み
• スタックオーバーフロー
• main関数の再帰呼び出し
• 練習問題
• 参考リンク
• 更新履歴

再帰呼び出し

少しイメージしづらい話ではありますが、関数は、自分自身を呼び出せます。このような呼び出しを、再帰呼び出し（リカーシブコール） (recursive call) といいます。

たとえば、次の関数は再帰呼び出しをしています。

void func(void)
{
    puts("Hello");
    func();  // 自分自身を呼び出す
}

構文としては何も特別なことはなく、いつもどおりに関数呼び出しを行うだけです。単に、自分自身の関数名を使えばよいだけです。

しかし、この関数のつくりでは、初回の func関数の呼び出しは、その中で func関数を呼び出し、その func関数がまた func関数を呼ぶ…これを永遠に繰り返してしまいます。初回の呼び出し以降、もう呼び出し元に処理が戻ってくることはありません。

実際にはいずれメモリを使いつくして強制終了となると思われます。あとで取り上げますが、関数呼び出しの際にメモリが消費されているため、永遠に関数呼び出しを続けることはできません。

再帰呼び出しの難しさの１つがここにあります。再帰呼び出しを行う場合には、どこかで再帰を打ち切るようにする必要があるのです。たとえば、次のようにすると、n回の再帰呼び出しで打ち切ることができます。

void func(int count)
{
    if (count <= 0) {
        return;  // これ以上再帰しない
    }

    puts("Hello");

    func(count - 1);  // 自分自身を呼び出す
}

func関数に引数を追加し、“Hello” を出力させる回数を指定できるようにしました。再帰呼び出しの際には、この値を -1 したものを渡すようにすることで、再帰のたびに引数の値が減っていきます。0以下の値を渡した呼び出しの際に、先頭にある if文の条件式が真になり、それ以上の再帰呼び出しを行わずに return で脱出します。

再帰呼び出しはイメージが難しいので、ここでちゃんと理解しておいてほしいのですが、この例で return文が実行されたとき、一気に、最初の func関数呼び出しの呼び出し元へ戻ってくるのではありません。たとえば、初回の呼び出し時に 5 という実引数を渡していたとします。

int main(void)
{
    func(5);  // "Hello" を 5回出力する

    // 省略
}

最終的に func関数内の return文が実行されるまでの間に、func(5)、func(4)、func(3)、func(2)、func(1)、func(0) という６回の関数呼び出しを行います。

return文を実行するのは６回目のときだけです。そして、このときの return文は func(0) の呼び出しから戻ります。その戻り先は、func関数内の終わりにある「func( count - 1 );」のところであって、初回の呼び出しを行った main関数のところではありません。

func(0) の呼び出しからは return文で戻りますが、それ以外の回の呼び出しは、func関数の末尾に到達したことで終わりを迎えています。func(1) の呼び出しが関数の末尾で終わり、func(1) を呼び出していた箇所へ戻る。次に、func(2) の呼び出しが関数の末尾で終わり、func(2) を呼び出していた箇所へ戻る・・・これを func(3)、func(4)、func(5) とさかのぼるように続けていき、func(5) の呼び出しが関数の末尾で終わったとき、初回の呼び出しを行った main関数のところに戻ってきます。

実際に完全なプログラムで試してみましょう。

#include <stdio.h>

void func(int count);

int main(void)
{
    func(5);  // "Hello" を 5回出力する
}

void func(int count)
{
    if (count <= 0) {
        return;
    }

    puts("Hello");

    func(count - 1);  // 自分自身を呼び出す
}

実行結果

Hello
Hello
Hello
Hello
Hello

何となく感じたかもしれませんが、再帰という手法は、本質的には繰り返し処理です。再帰呼び出しで実現できることは、while文などの繰り返し処理の手法で実現できます。

実現したいことが同じなら、繰り返し処理の方が速度面では効率的です。これは後で取り上げますが、関数呼び出しの仕組みによるものです。ただし、つねに一方が他方より優れるというわけではないので、本当に効率アップが必要なのであれば、両者を実際に試してみるべきでしょう。

一方で、適切な場面で再帰呼び出しを使うと、コードの記述が非常に簡潔になり、理解しやすいプログラムになることがあります。扱うデータ自体も再帰的な構造をしている場合などでは、再帰呼び出しの手法を使ったコードの方が自然で、分かりやすくなることが多いはずです。

ここで、再帰呼び出しを使うことが有効な実例を挙げるべきだと思いますが、Ｃ言語としては単に「関数は自分自身を呼び出せる」という事実があるだけなので、あまり深入りしないでおきます。再帰呼び出しを有効に使う実例は、大抵、アルゴリズムやデータ構造の話になってくるので、当サイトのアルゴリズムとデータ構造編の方でサポートしたいと思います。

たとえば、二分木（【データ構造】第７章）、クイックソート（【整列】第６章）、マージソート（【整列】第７章）などで、再帰呼び出しの話題が登場します。

関数呼び出しの仕組み

ここで少し、関数呼び出しの仕組みを整理しておきましょう。

まず、関数の内容（コード）はメモリ上に置かれています。関数ポインタという機能が使えるのは、コードがメモリ上にあるからです。

【上級】規格上に明確な取り決めはないのですが、通常、コードが置かれるメモリ領域と、データが置かれるメモリ領域は分けられています。関数ポインタとオブジェクトポインタとが同一の表現にならないことがあるのは、このためです（第３８章）。なお、コードが置かれるメモリ領域は、プログラム領域 (program area) とかテキスト領域 (text area) などと呼ばれています。

ここでのコードとは、Ｃ言語レベルでのソースコードではなく、コンパイルされた後の話です。Ｃ言語レベルでの記述量が少ないからといって、コードが使うメモリ領域も少ないとは限りません。言い換えると、コンパイルを終えると、関数のコード自身が使うメモリの量が分かります。そして、リンクを終えると、プログラム全体のコードが使うメモリ量が分かります。

プログラムの実行を開始すると、実行ファイルに書き込まれている情報に従って、コードをメモリに展開します。この時点で、各関数のメモリアドレスが確定しています。

プログラムを実行しているときには、「次に実行すべきコードはメモリ上のどこか」という情報がつねに管理されています。この情報は、CPU 内にあるレジスタという記憶装置に記憶されていますが、このような用途で使われるレジスタは特に、プログラムカウンタと呼ばれています。

関数呼び出しが実行されるときには、プログラムカウンタを目的の関数のコードがある場所に変更します。コードがメモリ上のどこに配置されているかは、プログラムを実行する際にメモリ上にコードが展開できているので、簡単に分かります。

しかし、呼び出し先のコードのメモリアドレスは簡単に分かっても、呼び出し元のメモリアドレスは分かりません。ある関数を呼び出している側は、プログラム内の複数の箇所にあるかもしれませんから、１つに定まりません。どこから呼び出されたのかを実行時に覚えておくしかありません。そのために、メモリのスタック領域と呼ばれる場所に情報を保存しておきます。

これも規格上に明確な定めはありませんが、ほとんどの環境ではスタック領域を使います。

スタック領域では、スタックという構造でデータを記憶します。この構造は、机の上に本を積み上げていくようなイメージになっています。データを記憶することは、本を１冊重ねるイメージ、データを取り出すことは、本を１冊手に取るイメージです。

本は積み重なっているので、一番上にしか置けず、一番上の本しか手に取ることができません。言い換えると、最後に置いた本しか手に取れません。スタックはこれと同じで、最後に記憶したデータだけが取り出せます。

スタックについての詳細は、アルゴリズムとデータ構造編【データ構造】第５章で解説しています。

関数呼び出しを行った先で、さらにほかの関数を呼び出すことがあります。A が B を、B が C を呼び出したとしたら、C から B へ、B から A へというように逆戻りするはずですから、呼び出し元の位置をスタックで記憶することは理に適っています。

つまり、「B を呼び出す側の位置を記憶して B を呼び出す」–>「C を呼び出す側の位置を記憶して C を呼び出す」–>「C の呼び出し元の位置を取り出して、そこへ戻る」–>「B の呼び出し元の位置を取り出して、そこへ戻る」のようにすれば実現できます。なお、このような仕組みは、コールスタックと呼ばれています。

実際にコールスタックに記憶する情報は、呼び出し元の位置情報だけではなく、引数や戻り値の情報を含むこともあります。また、関数内で定義されている自動記憶域期間を持った変数の値も、ここに含まれるかもしれません。いずれにしても、何が記憶されるのかは実行環境によって異なります。

スタックオーバーフロー

関数呼び出しのたびにスタック領域を消費するとなると、この領域を使いつくしてしまう可能性もあるということです。このような現象は、スタックオーバーフローと呼ばれています。スタックオーバーフローが起きると、一般的にはプログラムは異常終了します。

スタックオーバーフローを確認することは簡単で、無限に再帰呼び出しを繰り返す関数を作って、呼び出してみればいいだけです。次のプログラムを実行して放置しておくと、いずれスタックオーバーフローを起こします。

#include <stdio.h>

void func(void);

int main(void)
{
    func();
}

void func(void)
{
    puts("Hello");
    func();  // 自分自身を呼び出す
}

もちろん、スタックオーバーフローは起こらないようにする必要があります。きちんと対策を取るにあたって、まずはスタック領域の大きさを把握することです。

スタック領域の大きさは大抵、コンパイラに指示を与えることで変更できます。特に指示しなければ、Visual Studio では 1メガバイト、clang では 8メガバイトです。

Visual Studio の場合は、プロジェクトのプロパティから、[構成プロパティ] -> [リンカー] -> [システム] を選択して、[スタックのサイズの設定] に 0x1000000 のように入力することで、スタックサイズを変更できます。

再帰呼び出しでは、コールスタックに記憶する情報量が必然的に大きくなるので、スタックオーバーフローを起こしやすいと言えます。どうしてもスタック領域が不足してしまう場合には、再帰呼び出しを使うことをあきらめて、通常の繰り返し処理に置き換えなければならないかもしれません。

また、自動記憶域期間を持つ変数の情報がスタック領域を使う環境では（多くの環境ではそうです）、静的記憶域期間や、動的記憶域期間を持つように変更することも有効かもしれません。

main関数の再帰呼び出し

必要になることはまずありませんが、main関数を再帰呼び出しすることも許されています。

#include <stdio.h>

int main(void)
{
    static int count = 5;

    if (count >= 1) {
        puts("Hello");
        --count;
        main();
    }
}

実行結果

Hello
Hello
Hello
Hello
Hello

特にルールに違いはありません。初回の main関数が終了したときに、プログラムは終了します。

exit関数や abort関数のような関数は、プログラム自体を終了させるものなので、再帰呼び出しの途中であっても、プログラムが終了します。

【上級】C++ では、main関数だけは再帰呼び出しを許可しないことになっています。