再帰入門

CoddyのC++ジャーニー「論理と制御フロー」セクションの一部 — レッスン 45/56。

再帰は、関数が自分自身を呼び出して問題を解決するプログラミング手法です。ループを使用する代わりに、再帰関数は複雑な問題を、直接解決できる単純なケースに到達するまで、より小さく、似たような部分問題へと分解します。

すべての再帰関数には、2つの不可欠な構成要素が必要です。ベースケースは再帰を停止させる条件です。これがないと、関数は自分自身を永遠に呼び出し続けてしまいます。再帰ステップは、関数が変更されたパラメータを使用して自分自身を呼び出す部分であり、呼び出しのたびにベースケースに近づいていきます。

再帰を示す簡単なカウントダウンの例を次に示します：

void countdown(int n) {
    if (n <= 0) {           // ベースケース：nが0になったら停止する
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // 再帰ステップ：n-1で呼び出す
}

countdown(3)を呼び出すと、3を出力し、次にcountdown(2)を呼び出します。これは2を出力し、次にcountdown(1)を呼び出し、ベースケースに到達するまでこれを繰り返します。各関数呼び出しは、終了する前に次の関数の完了を待ち、最終的に元の呼び出し元まで戻る一連の呼び出しチェーンを作成します。

チートシート

再帰とは、問題をより小さな部分問題に分割することで解決するために、関数が自分自身を呼び出すことです。

すべての再帰関数には以下が必要です：

ベースケース: 再帰を停止させる条件
再帰ステップ: 変更されたパラメータで関数が自分自身を呼び出す

カウントダウン関数の例：

void countdown(int n) {
    if (n <= 0) {           // ベースケース
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // 再帰ステップ
}

自分で試してみよう

このレッスンにはコードチャレンジは含まれていません。