C言語再帰入門：再帰関数の書き方と使い方

C言語再帰入門

このチュートリアルでは、核心概念から自然数の合計を求める実践例まで、C言語での再帰の基礎を歩いていきます。

再帰関数とは、自分自身を呼び出す関数です。この自己参照技法である再帰を使うと、問題をより小さな同一の部分問題に分解して解決できます。

再帰の仕組み

void recurse() {
    /* 前処理 */
    recurse();
    /* 後処理 */
}
int main() {
    /* 初期セットアップ */
    recurse();
    /* フォローアップ */
}

再帰は停止条件（しばしばベースケースと呼ばれる）に達するまで繰り返されます。if…elseガードや類似の構造を使って、関数が最終的に終了し無限ループを避けることを保証します。

例: 再帰を使った自然数の合計

#include <stdio.h>
int sum(int n);
int main() {
    int number, result;
    printf("正の整数を入力: ");
    scanf("%d", &number);
    result = sum(number);
    printf("sum = %d", result);
    return 0;
}
int sum(int n) {
    if (n != 0)
        return n + sum(n-1); // 再帰呼び出し
    else
        return 0; // ベースケース
}

出力

正の整数を入力: 3
sum = 6

この例では、sum()はmain()からユーザー入力で呼び出されます。関数はnをデクリメントしながら自分自身を呼び出し、nがゼロに達するとベースケースで0を返し、再帰呼び出しがアンワインドしながら各中間値をmain()まで加算して戻ります。

再帰の利点と欠点

再帰は、ツリー探索、階乗計算、フィボナッチ数列など、再帰的構造に自然にマッピングされる問題でよりクリーンで読みやすいコードを生み出すことが多いです。しかし、関数呼び出しのオーバーヘッドとコールスタックによるメモリ使用量増加のため、反復ループより遅くなる可能性があります。パフォーマンスクリティカルなコードでは、反復解法やメモ化を検討してこれらのコストを軽減してください。

潜在的な欠点があるにもかかわらず、再帰はコンピュータサイエンスの基礎概念であり、多くのアルゴリズムとデータ構造操作の基盤となっています。再帰をマスターすることで、複雑な問題を優雅かつ精密に解決できるようになります。

C言語ユーザー定義関数の4つの実証済みパターン C言語ストレージクラス完全理解：スコープ・ライフタイム・パフォーマンス

C言語