再帰計算とχ2乗分布

1. 再帰計算
   
   
   1. 再帰的定義
      ある物を定義するとき、定義したい物を利用して定義する場合があります。これを再起的な定義と呼びます。再起的定義された物を処理するには、再帰的プログラミングが便利です。
      　再帰プログラミングそのものは、アルゴリズムではありませんが、再帰処理を利用するプログラムは少なくありませんので、ここで説明します。
      
      
   2. 階乗関数
      
      1. 階乗関数の再帰的定義
         階乗関数 fact(n) は次のように再帰的に定義できます．
         
         　fact(n)
         　 =1　　 : n=0
         　=n * fact(n-1)　: n>0
         
         これで，すべてのnに対する fact(n) の値が求められます．たとえば
         
         　fact(2) = 2*fact(1) = 2*1*fact(0) = 2*1*1 = 2
         
         このように，fact(n)の定義に fact(m) (m<n) の定義をそのまま用いることを再帰的定義と呼びます。
         この定義をそのまま用いてプログラムすることができます．
         
         
      2. 再帰的プログラム手法
         
         　先の定義に従いそのままプログラムを書くとつぎのようになります。fact(N) で fact(N-1) を呼び出しています。このように、自分自身を呼び出すことを再帰呼びだしと言います。
         　fact()の呼び出しは、init() で行っています。表示は、System.out.println() ですから、アプレットで結果を見るには、ツールメニューのJavaコンソールを利用します。
         
         

         import java.applet.*;
         
         public class Fact extends Applet {
         
           public void init() {
             fact(5);
           }
         
           int fact(int N) {
             int L;
             System.out.println("in fact(" + N + ")");
             if (N == 0)
               return (1);
             else {
               L = N * fact(N - 1);
               System.out.println("return fact;" + L);
               return (L);
             }
           }
         
         }

         実行例 　
         
         n=5の場合の実行例を示します。fact(5) の実行で まず、fact(4) を呼び出します。同様にfact(0) まで順に同じ関数が呼び出されますが、fact(0)では 値1 で計算が終了します。
         　すると、fact(0) の結果を用いてfact(1) の結果がでます。同様に fact(4) の結果を用いてfact(5) の結果がでます。
         
         in fact(5)
         in fact(4)
         in fact(3)
         in fact(2)
         in fact(1)
         in fact(0)
         
         return fact;1
         return fact;2
         return fact;6
         return fact;24
         return fact;120
         
         fact(5)= 120
         
         
   3. フィボナッチ数列
      
      1. 再帰処理が必要な場合
         先の階乗計算は、単純な繰り返しでプログラムができます。次の場合はどうでしょう。
         
         
      2. 再帰的定義
         フィボナッチ数列は次にように再帰的に定義されます。
         
         　Ｆ(1)＝Ｆ(2)＝１，
         　Ｆ(n)＝Ｆ(n-1)＋Ｆ(n-2)　　ｎ≧３の時、
         
         このＦ(n)は、単純な繰り返しでは計算できません。
         
         
      3. プログラム（ANSI)
         再帰処理をするプログラムは簡単です。定義をそのままプログラムしています。
         
         

           int fib(int N) {
             int L;
             System.out.println("in fib(" + N + ")");
             if (N == 1 || N == 2)
               return (1);
             else {
               L = fib(N - 1) + fib(N - 2);
               System.out.println("return fib;" + L);
               return (L);
             }
           }

         
         
      4. 実行例
         
         fib(5)　の計算課程を示します。
         
         in fib(5)
         in fib(4)
         in fib(3)
         in fib(2)
         in fib(1)
         return fib;2
         in fib(2)
         return fib;3
         in fib(3)
         in fib(2)
         in fib(1)
         return fib;2
         return fib;5
         
         
2. χ2乗分布の計算
   
   
   1. χ2乗分布の計算
      　再帰的に定義された χ2乗分布 の計算は定義から再帰的なプログラムを作成出来ます。
      
      

        double kai(int f, double x) {
          if (f == 1)
            return 1.0 / (Math.sqrt(2 * Math.PI * x * Math.exp(x)));
          if (f == 2)
            return 1.0 / (2 * Math.sqrt(Math.exp(x)));
          return (x / (f - 2)) * kai(f - 2, x);
      
        }
      }

      
      
   2. 軸と目盛り
      　ここでは、下のように、関数の x,y 軸と目盛りをつけて関数を表示します。ｘ軸の目盛りは、180から175まで、長さ5の直線で、表示します。目盛りの数値は、drawString() を利用します。文字の高さと幅の分だけ、表示位置を調整しています。
      

          for (int i = 1; i < 23; i++) {
            g.drawLine(ox + i * 20, oy + 180, ox + i * 20, oy + 175);
            g.drawString(Integer.toString(i), ox + i * 20 - 5, oy + 195);
          }
      
          
      

      
      
      
   3. ソース
      　
      

      import java.awt.*;
      import java.awt.event.*;
      import java.applet.*;
      
      public class kai2 extends Applet {
        int ox = 20, oy = 20;
        
        public void paint(Graphics g) {
          int px, py, nx, ny;
          for (int f = 1; f <= 9; f = f + 2) {
            px = 0;
            py = -1;
            //関数表示
            for (double x = 1.0; x < 23.0; x = x + 0.2) {
              nx = (int) (x * 20) + ox;
              ny = (int) ((0.3 - kai(f, x)) * 600) + oy;
              if (py > 0)
                g.drawLine(px, py, nx, ny);
              if (Math.abs(x - 1.4) < 0.01)
                g.drawString(Integer.toString(f), ox + 30, ny - 5);
              px = nx;
              py = ny;
            }
          }
          
          //軸の表示
          g.drawLine(ox + 20, oy + 180, 23 * 20 + ox, oy + 180);
          g.drawLine(ox + 20, oy + 180, ox + 20, 20);
          
          //ｘ軸目盛り
          for (int i = 1; i < 23; i++) {
            g.drawLine(ox + i * 20, oy + 180, ox + i * 20, oy + 175);
            g.drawString(Integer.toString(i), ox + i * 20 - 5, oy + 195);
          }
          for (double y = 0.0; y <= 0.3; y=y+0.05) {
            int fy=(int)((0.3-y)*600);
            g.drawLine(ox + 20, oy + fy, ox + 15, oy + fy);
            String st="";
            if(Double.toString(y).length()>4) st=Double.toString(y).substring(0,4);
            else st=st=Double.toString(y);
            g.drawString(st, ox - 10, oy + fy);
          }
          g.drawString("χ2分布",100,50);
      
        }
        
      // 関数の計算 
        double kai(int f, double x) {
          if (f == 1)
            return 1.0 / (Math.sqrt(2 * Math.PI * x * Math.exp(x)));
          if (f == 2)
            return 1.0 / (2 * Math.sqrt(Math.exp(x)));
          return (x / (f - 2)) * kai(f - 2, x);
      
        }
      
      }

      
      
3. 演習
   
   
   1. 合計
      次の、組み合わせ数の再帰的定義を利用して、組み合わせ数 _ｎＣ_ｒ を計算するプログラムを作成して下さい。
      
      _nＣ₀=1,_nＣ_n=1;
      _ｎＣ_ｒ＝_ｎ-1Ｃ_r＋_ｎ-1Ｃ_r-1 1<r<n