再起関数の基礎

32 と 24 の GCM は 8 です

C# の再起関数(recursive function) で GCM(最大公約数)を求めます。

前田稔(Maeda Minoru)の超初心者のプログラム入門

プログラムの説明

  1. C:\Data\C#\ のフォルダーに次のファイルを格納して下さい。
    初心者の方は テンプレートを使って Hello C# を参照して下さい。
    [空のプロジェクト] Hello C# から構築することも出来ます。
    /********************************************/
    /*★ C# GCM Function Program    前田 稔 ★*/
    /********************************************/
    using System;
    
    class console
    {
        public static int Main()
        {
            int x = 32;
            int y = 24;
    
            int ans = gcm(x, y);
            Console.WriteLine("{0} と {1} の GCM は {2} です",x,y,ans);
            System.Console.ReadLine();
            return 0;
        }
    
        static int gcm(int n, int m)
        {
            if (n==m)       return n;
            if (n>m)        return gcm(n-m,m);
            return gcm(m,n);
        }
    }
    
  2. 関数(method) の基礎は メソッド(method) の定義 を参照して下さい。
    GCM の説明は 分数の計算 を参照して下さい。
  3. x と y に格納された値の GCM(最大公約数)を gcm(x, y); 関数で求めて表示します。
            int x = 32;
            int y = 24;
            int ans = gcm(x, y);
        
  4. gcm 関数の中から gcm 関数を呼び出していることに注目して下さい。
    このように自分自身を呼び出す関数を「再起関数(recursive function)」と言います。
    今回の gcm 関数の場合は、パラメータを設定し直して呼び続けるだけなので、解り易いのでは無いでしょうか。 (^_^;)

【演習】

  1. gcm 関数に渡されるパラメータ(n, m) をトレースして、再起関数の実行の流れを理解して下さい。
  2. パラメータの値を変えて試して下さい。

【NOTE】

  1. 再起の考え方はとっつき難く、慣れるまで大変でしょうがその威力は抜群でぜひ身に付けたいものです。
    私の経験では「ループは全て再起」になり、完成したプログラムは非常にスマートです。 (^_^;
  2. 再起にとりつかれると何でも再起で処理したくなりますが多用は禁物です。
    作成した本人はともかく、論理の流れが他人には非常にわかり難いのです。
    再起処理は、しっかりした構想の下「処理できる確信」を持ってプログラムして、思い通りの結果が出て始めて その考え方が正しいことが証明されるのです。
    正しく動かない再起プログラムほど始末に悪いものはありません。
    再起処理のプログラムは、自分の責任で完成させる力を身につけてから挑戦して下さい。
  3. 再起プログラムの構成。
    1. 再起もループと同じように初期値の設定が必要です。
      普通は関数を最初にコールするときに初期値を設定します。
    2. 一般的に再起関数の先頭で、終了条件を判定して関数からリターンします。
    3. 「何か処理をして」関数を再起コールします。
      このとき次の条件を満たすことが必要です。
      • 関数を繰り返し呼び出すことにより「処理が進展する」こと。
      • 関数を繰り返し呼び出すことにより「やがて終了条件に達する」こと。
    4. 再起関数には「コールする前」と「ワンレベル再起関数から戻ったとき」の二箇所で処理を行うことが出来ます。
      「コールする前」に処理する代表的なプログラムは最大公約数を求めるプログラムです。
      「ワンレベル再起関数から戻ったとき」に処理する代表的なプログラムは階乗を求めるプログラムです。
      もちろん「コールする前」と「ワンレベル再起関数から戻ったとき」の両方で処理することも出来ます。
  4. 再起関数の代表は「リスト処理」で、その中でも LISP 言語は芸術的と思われるほどスマートです。
    機会があればぜひ挑戦してみて下さい。

超初心者のプログラム入門(C# Frame Work)