Linux C プログラミングチュートリアル パート18: 再帰関数

使用するプログラミング言語に関係なく、コーディングを進めるにつれて、コードを簡潔で読みやすく、理解しやすくする概念を学ぶことになります。C言語にもそのような概念がいくつかあります。その一つが「再帰関数」であり、この記事で説明します。

再帰関数とは、自分自身を呼び出す関数です。呼び出しは、関数の本体内から直接行うことも、問題の関数によって呼び出される他の関数内から間接的に行うこともできます。

以下は直接再帰の例です:

int func (int a)  
{  
    //ステートメント  
  
    func(a-1);  
  
    // ステートメント  
  
    return 0;  
}

そして、こちらが間接再帰の例です:

int func (int a)  
{  
    //ステートメント  
  
    func_new(a);  
  
    // ステートメント  
  
    return 0;  
}  
  
int func_new(int b)  
{  
    //ステートメント  
  
    func(b-1);  
  
    //ステートメント  
  
    return 0;  
}

冒頭で述べたように、再帰はコンパクトなコードを実現するのに役立ちます。これは書きやすいだけでなく、理解しやすく、レビューもしやすいです。この利点をより明確にするために、例を見てみましょう。

皆さんは階乗の概念を聞いたことがあると思います。知らない方のために説明すると、階乗とは、整数をその整数より小さいすべての正の整数で掛けた結果です。例えば、5の階乗は5x4x3x2x1で、120に等しいです。

こちらは、数の階乗を求めるための簡単なコードです:

#include   
  
int main()  
{  
 int a = 0, i = 0, fact = 1;  
 printf("数を入力してください: ");  
  
 scanf("%d", &a);  
   
 for(i=1; i<=a; i++)  
 {  
 fact = fact * i;  
   
 }  
 printf("その数の階乗は: %d ", fact);  
 return 0;  
}

このコードは、Cプログラムを通じて数の階乗を計算する方法を知ってもらうためのものです。このプログラムは、結果の精度に影響を与える可能性のある特異ケースには対処していません。

これは、再帰関数を使用せずに数の階乗を計算する方法の一つです。次に、再帰を使用して階乗を計算するコードを見てみましょう。

#include   
  
int factorial (int b)  
{  
 if(!b)  
 return 1;  
   
 return (b * factorial(b-1));  
}  
  
int main()  
{  
 int a = 0, fact = 1;  
 printf("数を入力してください: ");  
  
 scanf("%d", &a);  
   
 fact = factorial(a);  
   
 printf("その数の階乗は: %d ", fact);  
 return 0;  
}

ご覧の通り、実際に階乗を計算する関数「factorial」は非常にコンパクトです。そして、注意深く見ると、非常に理解しやすいことがわかります。

何が起こっているのかわからない方のために説明すると、ユーザーが入力した値、例えば5は、最初に「main」関数から呼び出されたときに「factorial」関数に渡されます。「factorial」関数内では、入力値がゼロかどうかを確認するチェックがありますが、最初に入力値「5」で呼び出されたときはそれは真ではありません。

次に、return文には5と「factorial(4)」の戻り値を掛ける式が含まれています。これで「factorial」関数が再度実行され、次の式に到達します: return (4 * factorial(3))。そして再びこれらのステップが繰り返されます。

広く見ると、これらの関数呼び出しがどのようにスタックされるかは次の通りです:

• 5 * factorial(4)
• 4 * factorial(3)
• 3 * factorial(2)
• 2 * factorial (1)
• 1 * factorial (0)

今、factorial(0)が実行されると、「factorial」関数内の「if」条件が真になり、値「1」が返されます。これで、上記のリストにある呼び出しがどのように完了するかは次の通りです（前のリストの最後のエントリとこのリストの最初のエントリを比較してください）:

• 1 * 1
• 2 (11)
• 3 (2(1*1))
• 4 (3(2(11)))
• 5 (4 (3(2(1*1))))

これは実質的に5 4 3 2 1であり、結果として120、すなわち5の階乗になります。

これが再帰関数の動作です。これまで挙げた再帰関数の利点には疑いの余地はありませんが、いくつかの欠点もあります。

例えば、上記の例では、「factorial(0)」の呼び出しが完了するまで、すべての以前の「factorial」呼び出しが関数の処理が完了するのを待っていました。再帰呼び出しごとに自動変数やローカル変数がメモリを占有することは言うまでもありません。

したがって、再帰を使用する場合、ストレージスペースの節約は実質的にありません。さらに、コードの実行が速くなる保証もありません。再帰関数の真の利点は、データ構造を扱うときにあります。これは、このCチュートリアルシリーズの後の部分で説明します。

結論

結論として、日常のコーディング作業で再帰関数を頻繁に使用することはないかもしれませんが、知っておくべき重要な概念です。ここで紹介した例を試してみて、再帰関数の概念をさらに理解するために調整してみてください。