C言語の再帰と引数渡し

再帰 (Recursion) と C 言語における関数への引数の渡し方

再帰とは、関数が自分自身を呼び出すことによって問題を解決する手法です。再帰は特に分割統治法（Divide and Conquer）のアルゴリズムにおいて頻繁に利用されます。再帰を利用することで、問題を小さな部分問題に分割し、それを順番に解くことで全体の問題を解決することが可能になります。

C 言語における再帰の基本的な使い方、そして関数に引数（引数）をどのように渡すかを理解することは、C 言語を効果的に使うための重要なスキルです。

再帰の基本的な概念

再帰の基本は、関数が自分自身を呼び出すことです。しかし、無限に呼び出しが続くことは望ましくないため、必ず終了条件（ベースケース）を設ける必要があります。終了条件がない場合、無限再帰となり、プログラムがクラッシュしてしまいます。

以下は、再帰を用いて階乗を計算する簡単な例です。

c
CopyEdit
#include 

// 再帰的に階乗を計算する関数
int factorial(int n) {
    // ベースケース：nが0または1の場合
    if (n == 0 || n == 1) {
        return 1;
    }
    // 再帰的呼び出し
    return n * factorial(n - 1);
}

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

この例では、factorial 関数が自分自身を呼び出しており、n が 1 になるまで再帰を続け、最後に計算結果を返します。

再帰の動作

再帰関数は、呼び出し時に新しいスタックフレームを作成し、その中で再帰的な処理を行います。関数が呼び出されるたびに、その関数の実行がスタックに積まれていきます。再帰が終了条件に達すると、順番にスタックから返り値が戻り、最終的に最初の呼び出し元に結果が返されます。

再帰関数のメリットとデメリット

メリット:

1. 問題が自然に再帰的な構造を持っている場合、コードが簡潔になる。
2. 複雑なループや手続き的なコードが再帰を使用することでシンプルに書ける。

デメリット:

1. 再帰呼び出しが深くなると、スタックオーバーフローを引き起こす可能性がある。
2. 再帰関数は通常、ループよりもオーバーヘッドが大きくなるため、パフォーマンスが低下することがある。

引数の渡し方

C 言語において関数に引数を渡す方法は、主に以下の 2 種類です。

1. 値渡し（Call by Value）:
   引数として渡された変数の値が関数内にコピーされる方式です。この場合、関数内で引数の値を変更しても、呼び出し元の変数には影響を与えません。

   c
   CopyEdit
   void passByValue(int x) {
       x = 10; // 関数内でxを変更しても呼び出し元には影響しない
   }
   
   int main() {
       int num = 5;
       passByValue(num);
       printf("num is %d\n", num);  // 5が出力される
       return 0;
   }
   

2. 参照渡し（Call by Reference）:
   ポインタを使って引数を渡す方法です。これにより、関数内で引数の値を変更すると、呼び出し元にも変更が反映されます。

   c
   CopyEdit
   void passByReference(int *x) {
       *x = 10; // 関数内でポインタ経由で値を変更する
   }
   
   int main() {
       int num = 5;
       passByReference(&num);
       printf("num is %d\n", num);  // 10が出力される
       return 0;
   }
   

再帰と引数の渡し方

再帰関数にも引数を渡す際、通常は値渡しを使いますが、特定の状況下ではポインタを用いて参照渡しを行うこともあります。たとえば、再帰の過程で関数内で変数の変更を呼び出し元にも反映させたい場合です。

以下は、再帰とポインタを組み合わせてリストの合計を計算する例です。

c
CopyEdit
#include 

// 再帰的にリストの合計を計算する関数
int sumList(int *arr, int index, int size) {
    // ベースケース：リストの終わりに達した場合
    if (index == size) {
        return 0;
    }
    // 再帰的呼び出し
    return arr[index] + sumList(arr, index + 1, size);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Sum of array is %d\n", sumList(arr, 0, size));
    return 0;
}

このプログラムでは、sumList 関数が再帰的にリストを走査し、合計値を計算します。arr 配列へのポインタを渡し、インデックスと配列のサイズを引数として利用しています。

結論

再帰は強力な技法であり、特に自然に分割可能な問題に対して非常に有効です。しかし、無限再帰やスタックオーバーフローを避けるために、終了条件を必ず設定する必要があります。C 言語では、引数を値渡しまたは参照渡しで渡すことができ、再帰関数においては、引数の渡し方を適切に選択することで、効率的なプログラムを作成することができます。