C 再帰

再帰とは、関数の定義の中で関数自身を使用する方法のことです。

例を挙げます:
昔々、ある山がありました。山の中に寺があり、寺には年老いた和尚がいて、小僧に物語を語っていました。その物語とは?「昔々、ある山がありました。山の中に寺があり、寺には年老いた和尚がいて、小僧に物語を語っていました。その物語とは?『昔々、ある山がありました。山の中に寺があり、寺には年老いた和尚がいて、小僧に物語を語っていました。その物語とは?……』」

構文の形式は次のとおりです:

void recursion() { statements; ... ... ... recursion(); /*関数が自分自身を呼び出す*/ ... ... ... } int main() { recursion(); }

フローチャート:

C言語は再帰をサポートしています。つまり、関数は自分自身を呼び出すことができます。ただし、再帰を使用する際、プログラマーは関数から抜け出す条件を定義する必要があります。そうしないと無限ループに陥ります。

再帰関数は、数の階乗の計算やフィボナッチ数列の生成など、多くの数学的問題を解決する上で極めて重要な役割を果たします。

数の階乗

次の実例では、再帰関数を使用して指定された数の階乗を計算します:

実例

#include <stdio.h> double factorial(unsigned int i) { if(i <= 1) { return 1; } return i * factorial(i - 1); } int main() { int i = 15; printf("%d の階乗は %f です\n", i, factorial(i)); return 0; }

上記のコードをコンパイルして実行すると、次の結果が得られます:

15 的阶乘为 1307674368000.000000

フィボナッチ数列

次の実例では、再帰関数を使用して指定された数のフィボナッチ数列を生成します:

実例

#include <stdio.h> int fibonaci(int i) { if(i == 0) { return 0; } if(i == 1) { return 1; } return fibonaci(i-1) + fibonaci(i-2); } int main() { int i; for (i = 0; i < 10; i++) { printf("%d\t\n", fibonaci(i)); } return 0; }

上記のコードをコンパイルして実行すると、次の結果が得られます:

0    
1    
1    
2    
3    
5    
8    
13    
21    
34
その他の拡張