[C/C++] 再起呼び出しの書き方と使い方

2023年6月11日2024年9月7日

当ページのリンクには広告が含まれています。

再起呼び出しは、Cプログラミングにおいて効率的なコードを書くために必須の概念です。
この記事では、再起呼び出しの基本と使い方を初心者向けにわかりやすく解説します。

再起呼び出しとは？

再起呼び出しとは、ある関数からその関数自身を呼び出すことです。
これにより、短いコードで繰り返し処理を行うことが可能になります。最初は難しく感じると思いますが、慣れてくるとコードが簡潔かつ効率的に書けるようになります。

再起呼び出しを使うことのメリットとデメリット

メリット

for文やwhile文を使って繰り返し処理をするより、簡潔で効率的なコードになる
コードが短くなるので、再起呼び出しに慣れている人は、その関数が何をしているかを早く理解できる

デメリット

関数呼び出しが深くなるため、スタックオーバフローが発生するリスクがある
初心者にはコードの理解が難しい
複数回の関数呼び出しによりパフォーマンスが低下する

これらの性質を理解して、適切に使うことが重要となります。

関数呼び出しの書き方

再起呼び出しを書く際には、「ベースケース」と「再起ケース」の2つを含める必要があります。

ベースケース：
再起呼び出しを止めるための条件のこと。
これがないと関数は自分自身を無限に呼び出し続けてしまいます。
再起ケース：
関数が自分自身を呼び出す部分のこと。

int Func(int data)
{
    int ret;
    if(再起呼び出しを止める条件){  // ベースケース
        return data;
    }
    ret = Func(data);  // 再起ケース
    return ret;
}

再起呼び出しの実装例

階乗を計算する関数をfor文を使う場合と、再起呼び出しを使う場合で比較してみます。

// for文で階乗を計算する例
int Func1(int n)
{
    int ret = 1;
    for(int i=1; i<=n; i++){
        ret *= i;
    }
    return ret;
}

// 再起呼び出しで階乗を計算する例
int Func2(int n)
{
    if(n == 0){
        return 1;
    }else{
        return n * Func2(n - 1);
    }
}

階乗の計算のような単純なパターンでは、あまり差が感じられないと思いますが、より複雑な関数になると可読性やコードの長さに大きな差が出てきます。

この再起呼び出し関数では、Func2が自分自身を呼び出し、引数が0になったときに再起呼び出しを終了し、それ以外の場合は自身を(引数-1)で再起呼び出しします。

例えば、引数に3を渡した場合、以下のような処理フローとなります。

再起呼び出しの使いどころ

再起呼び出しは、以下のような状況でよく使われます。

階乗やフィボナッチ数列などの計算
ツリー構造のデータの巡回や二分探索をする場合
バックトラッキング（全ての解を見つけ出すために、一度試した解を取り消して別の解を試す手法）が必要な場合

再起呼び出しを使う際の注意点

終了条件を明確にすること
再起呼び出しを行う関数はいつかは必ず終了する必要があります。
終了条件に不具合があると、無限ループに陥ってしまい、スタックオーバフローを引き起こしてしまいます。これを避けるために、終了条件を明確に設定し、再起呼び出しを確実に終了することが重要です。
関数呼び出しの深さを意識すること
再起呼び出しは、関数呼び出しでスタックメモリを消費します。呼び出しの深さが深いと、メモリが足りなくなりスタックオーバーフローが発生する可能性があります。メモリが足りていてもメモリを大量に消費してしまう可能性があります。再起呼び出しの深さを事前に予測して、適切な制限や終了条件を設定することが重要です。
処理速度に影響がある
関数呼び出しにはオーバーヘッドがあるため、同じ処理をループで行うよりも遅くなる場合が多いです。処理速度を落としたくない場合や、あまり複雑ではない処理の場合は、for文やwhile文で実装した方が良い場合があります。
デバッグが難しくなる
再起呼び出しのコードは直感的に読めない場合があり、コードの可読性が低下する可能性があります。このため、再起呼び出しが深すぎる場合や複数の再起パスが存在する場合、デバッグが難しくなります。