再帰的定義

ベジェ曲線
n次のベジェ曲線も再帰的に定義されます。これから、図形的な作図が可能になります。

下図は t=1/2 の位置を作図で求める方法です

概要
自分自身を使用して定義を行うことを再帰的な定義と言います。場合によって有効な定義です。
再帰的な定義は再帰的なプログラムで処理できます。

フィボナッチ数
フィボナッチ数列は次にように再帰的に定義されます。

　Ｆ(1)＝Ｆ(2)＝１，
　Ｆ(n)＝Ｆ(n-1)＋Ｆ(n-2)　　ｎ≧３の時、

このＦ(n)の計算は、単純な繰り返しでは計算できません

階乗関数の場合
階乗関数 fact(n) は次のように再帰的に定義できます．

　fact(n)
　 =1　　          : n=0
　 =n * fact(n-1)　: n>0

これで，すべてのnに対する fact(n) の値が求められます．

組み合わせ数
組み合わせ数も再帰的に定義されます。これからパスカルの三角形が生成できます。
_ｎＣ_ｒ＝_ｎ-1Ｃ_r＋_ｎ-1Ｃ_r-1

再帰的プログラム
次のC言語の関数 Fact(N) は n! を計算します。先の定義に従いそのままプログラムを書くとつぎのようになります。

  long Fact(long N)
    {
      long L;
      printf("in Fact(%d)\n", N);
      if (N == 0) return(1);
    else {
      L=N*Fact(N-1);
      printf("return fact=%ld\n",L);
      return(L);
    }
  }
 void main()
  { 
    int Num;
    printf("number:");
    scanf("%d",&Num);
    printf("\nfact(%d)= %ld \n",
      Num,Fact(Num));
  }