Cの再帰

再帰は、関数が自分自身を呼び出して問題を解決する手法です。

このレッスンでは、次のことを学びます。

• 再帰とは何か、どのように動作するか
• 再帰関数を実装する方法
• 再帰と反復の違い

再帰とは

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

構文の例：

void function() { function(); // Recursive call }

すべての再帰関数には、無限再帰を防ぐための基底ケースが必要です。

例：再帰

このプログラムは、5から1までの数値を出力して再帰の仕組みを示します。

#include <stdio.h>

void countDown(int n) {
    if (n <= 0) return; // Base case
    printf("%d\n", n);
    countDown(n - 1); // Recursive call
}

int main() {
    countDown(5);
    return 0;
}

再帰の基底ケース

再帰関数には、再帰を停止するための基底ケースを含める必要があります。

例：

if (n == 0) return;

基底ケースがないと、関数は無限に自分自身を呼び出し続け、スタックオーバーフローが発生します。

例：再帰を使った階乗

このプログラムは、再帰を使って数値の階乗を計算します。

#include <stdio.h>

int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1);
}

int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

再帰と反復の比較

再帰と反復（ループ）は同じ結果を得られますが、仕組みは異なります。

違い：

• 再帰は関数呼び出しを使用するため、より多くのメモリを必要とします。
• 反復はループを使用し、一般的により効率的です。
• 再帰は、木構造の走査などの問題でコードをシンプルにできます。

例：フィボナッチ数列（再帰）

このプログラムでは、再帰を使用してフィボナッチ数列を計算します。

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    printf("Fibonacci(5): %d\n", fibonacci(5));
    return 0;
}

再帰はいつ使うか

再帰は、次のような問題に役立ちます。

• 木構造の走査
• バックトラッキング（迷路の解法など）
• 階乗やフィボナッチ数列などの数学的な問題

まとめ

このレッスンでは、次のことを学びました。

• 再帰とは何か、どのように動作するか
• ベースケースの重要性
• 再帰と反復の違い

次は、C言語の配列と文字列について学びます。