C言語編 第53章 再帰呼び出し

先頭へ戻る

この章の概要

この章の概要です。

再帰呼び出し

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

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

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

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

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

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

再帰呼び出しの難しさの1つがここにあります。再帰呼び出しを行う場合には、どこかで再帰を打ち切るようにする必要があるのです。例えば、次のようにすると、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) という6回の関数呼び出しを行うことになります。
return文を実行するのは6回目のときだけであり、このときの 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回出力する */

    return 0;
}

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

    puts( "Hello" );

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

実行結果

Hello
Hello
Hello
Hello
Hello

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

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

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


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

例えば、二分木(【データ構造】第7章)、クイックソート(【整列】第6章)、マージソート(【整列】第7章)などで、再帰呼び出しの話題が登場します。

関数呼び出しの仕組み

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

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

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

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

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

さて、プログラムを実行しているときには、「次に実行すべきコードはメモリ上のどこか」という情報が常に管理されています。これは、CPU 内に存在するレジスタという記憶装置で記憶されており、プログラムカウンタとか PCレジスタと呼ばれています。

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

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

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

スタック領域では、スタックという構造でデータを記憶します。この構造は、机の上に本を積み上げていくようなイメージになっています。データを記憶することは、本を1冊重ねるイメージ、データを取り出すことは、本を1冊手に取るイメージです。ポイントは、本は積み重なっているので、一番上にしか置けず、一番上の本しか手に取ることができません。言い換えると、最後に置いた本しか手に取れません。 スタックはこれと同じで、最後に記憶したデータだけが取り出せます。

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

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

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

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

スタックオーバーフロー

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

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

#include <stdio.h>

void func(void);

int main(void)
{
    func();

    return 0;
}

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

言うまでもなく、スタックオーバーフローは起こらないようにする必要があります。きちんと対策を取るにあたっては、まずはスタック領域の大きさを把握することです。スタック領域の大きさは大抵、コンパイラに指示を与えることで変更することができます。特に指示しなければ、VisualStudio では 1メガバイト、clang では 8メガバイトです。

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

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

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

main関数の再帰呼び出し

滅多にないことですが、main関数を再帰呼び出しすることも許されています。

#include <stdio.h>

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

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

    return 0;
}

実行結果

Hello
Hello
Hello
Hello
Hello

特にルールに違いはありません。初回の main関数が終了したときに、プログラムは終了します。exit関数abort関数のような関数は、プログラム自体を終了させるものなので、再帰呼び出しの途中であっても、プログラムが終了します。

C++ では、main関数だけは再帰呼び出しを許可しないことになっています。しかし、VisualStudio、clang のいずれでも main関数の再帰呼び出しを行うことができるようです。


練習問題

問題① 階乗を計算する関数を再帰呼び出しを利用して作成して下さい。また、再帰呼び出ししない方法でも作成して下さい。

問題② 次のようなプログラムがあります。

#include <stdio.h>

struct Data_tag {
    int num;
    struct Data_tag* next;
};

static struct Data_tag gHead;

int main(void)
{
    struct Data_tag data00;
    struct Data_tag data01;
    struct Data_tag data02;

    gHead.num = 0;
    gHead.next = &data00;

    data00.num = 15;
    data00.next = &data01;

    data01.num = 30;
    data01.next = &data02;

    data02.num = 45;
    data02.next = NULL;

    return 0;
}

Data_tag構造体のメモリアドレスを渡すと、ヌルポインタに行き着くまで nextメンバを辿っていき、その過程で numメンバの内容を出力する関数を作成して下さい。再帰呼び出しを使ったものと、使わないものをそれぞれ作成して下さい。


解答ページはこちら

参考リンク



更新履歴

'2018/4/20 「NULL」よりも「ヌルポインタ」が適切な箇所について、「ヌルポインタ」に修正。

'2018/4/2 「VisualC++」という表現を「VisualStudio」に統一。

'2018/3/28 全面的に文章を見直し、修正を行った。
章のタイトルを変更(再帰 -> 再帰呼び出し)
スタックオーバーフロー」の項の内容の一部を、「関数呼び出しの仕組み」に分離した。
「末尾再帰の除去」の項を削除。
main関数の再帰呼び出し」の項を追加。

'2018/1/5 Xcode 8.3.3 を clang 5.0.0 に置き換え。

'2015/8/30 Xcode (OS X) に対応。
スタックサイズの設定を変更する方法を、コラムとして追記。

'2011/7/9 新規作成。



前の章へ(第52章 可変個引数)

次の章へ(第54章 乱数)

C言語編のトップページへ

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS