C・C++の再帰と呼び出しスタックをCとC++で実行

はじめに

再帰は、問題を同じ種類のより小さな問題に変えて解く手法です。どの再帰関数にも基底ケース（base case）が必要で、呼び出しのたびにそこへ近づかなければなりません。そうでないと、プログラムは関数を永遠に呼び続けます。

大切なポイント

空のデータ、要素が1つのデータ、重複を含むデータ、並べ替え済みのデータで試しましょう。
まず正しく動かし、最適化はその後にしましょう。
実際のコードでは、標準ライブラリの既製の関数を優先しましょう。

動きで理解する

ステップを押して各呼び出しを追いましょう。新しい呼び出しはコールスタックに積まれ、それぞれ呼び出し元に値を返します。

CとC++のコード例

C

実行 →

main.c

#include <stdio.h>

unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main(void) {
    printf("%llu\n", factorial(6));
}

実行結果

C++

実行 →

main.cpp

#include <iostream>

constexpr unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main() {
    constexpr auto value = factorial(6);
    std::cout << value << '\n';
}

実行結果

CとC++の比較

関数factorialはnumberが2未満なら1を返し（これが基底ケース）、それ以外はnumber * factorial(number - 1)を返します。関数を呼ぶたびに呼び出しスタック（call stack）のメモリを少しずつ使うので、このアルゴリズムはO(n)の時間とO(n)のスタックを使います。C++のバージョンは関数にconstexprを付けているので、値をコンパイル時に計算できます。大きな入力では入力値をチェックし、再帰の代わりにループを使うのが一般的です。

C

ループ、ポインタ、長さ、一時的なバッファをすべて明示的に書きます。

C++

イテレーターと標準アルゴリズムが、処理とデータの保存方法を切り離します。

発展問題

両方のバージョンを実行し、コードを書き換えて、それぞれの言語がもたらす安全性の違いを観察しましょう。

比較を1回ずつ紙の上でたどってみましょう。
重複した値や、とても大きい値・小さい値で試しましょう。
自分で書いたコードの実行時間を測り、標準ライブラリと比べましょう。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ