C++再帰完全ガイド：概念、実例、ベストプラクティス

C++ 再帰をマスターする

このチュートリアルでは、C++の再帰関数を探求し、その仕組みを理解し、実践的な例を見ていきます。

自分自身を呼び出す関数を再帰関数と呼びます。この強力な技法を再帰と呼びます。

C++ での再帰の仕組み

void recurse()
{
    // 再帰前のコード
    recurse(); // 再帰呼び出し
    // 再帰後のコード
}

int main()
{
    // セットアップコード
    recurse();
    // クリーンアップコード
}

以下の図は再帰の繰り返し自己呼び出しの性質を示しています。

再帰はベース条件が満たされるまで続きます。

無限再帰を避けるため、条件ガード（例: if…else）で、再帰呼び出しを行うブランチを1つだけに制限します。

実例 1: 再帰で階乗を計算

// n! = 1 × 2 × … × n を計算
#include <iostream>
using namespace std;

int factorial(int);

int main()
{
    int n, result;
    cout << "Enter a non-negative number: ";
    cin >> n;
    result = factorial(n);
    cout << "Factorial of " << n << " = " << result;
    return 0;
}

int factorial(int n)
{
    if (n > 1)
        return n * factorial(n - 1);
    else
        return 1;
}

出力

Enter a non-negative number: 4
Factorial of 4 = 24

階乗プログラムの仕組み

factorial() 関数は繰り返し自分自身を呼び出し、毎回 n を1ずつ減らします。n が1以下になると1を返し、再帰が巻き戻って最終結果を生成します。

C++ で再帰を使うメリットとデメリット

以下に再帰の主な利点と欠点をまとめます。

利点

簡潔で表現力豊かなコードになる
ツリー、グラフ、組み合わせ探索など、再帰的な性質を持つ問題の自然な解法に不可欠

欠点

同等の反復的アプローチより多くのスタック領域を消費
プロセッサオーバーヘッドが追加で発生する可能性
深いコールスタックによりデバッグがより困難になる

再帰をいつ、どう使うかを理解することで、一般的な落とし穴を避けながら、よりクリーンで保守しやすいC++コードが書けます。

C++デフォルト引数完全ガイド：仕組み、実例、ベストプラクティス C++配列完全ガイド：宣言、初期化、アクセス、実践例

C言語