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

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

再起呼び出しとは？

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

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

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

関数呼び出しの書き方

再起呼び出しを書く際には、「ベースケース」と「再起ケース」の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文で実装した方が良い場合があります。

• デバッグが難しくなる
  再起呼び出しのコードは直感的に読めない場合があり、コードの可読性が低下する可能性があります。このため、再起呼び出しが深すぎる場合や複数の再起パスが存在する場合、デバッグが難しくなります。

まとめ

再起呼び出しは強力なプログラミングテクニックであり、適切に使うことで複雑な処理でも簡潔にコードを書くことができます。ただし、再起呼び出しを使うときには、終了条件の設定やスタックオーバーフローのリスクなど、考慮すべき点も多いので、これらを理解して適切に使用することが重要です。