0

この場合、数値のすべての素数の倍数を表示する次のメソッドがあります。このメソッドの再帰的な動作のほとんどは理解していますが、数値5を出力した後、混乱します。なぜnが10に戻るのですか。前の呼び出しで5だったとき（つまり、3番目の再帰メソッドを実行したとき）

public class Tester {     

    static boolean isPrime(int p)
    {
        for(int i = 2; i < p; i++)
        {
            if(p % i == 0) return false;
        }
        return true;
    }


   public static void primeFactors(int n)
   {
       primeFactorsR(n, n-1);
   }

   static int count1 = 1, count2 = 1, count3 = 1, count4 = 1;

   public static void primeFactorsR(int n, int m)
      {
         if(isPrime(n))
         {
             System.out.println(n);
             System.out.println("method1 " +count1++);
         }     
         else
            if(n % m == 0)
            {
               System.out.println("n " + n + " m " + m);
               System.out.println("method2: " + count2++);
               primeFactorsR(m, m-1);

               System.out.println("n " + n + " m " + m);
               System.out.println("method3: " + count3++);
               primeFactorsR(n/m, (n/m)-1);              
            }
            else
            {
               System.out.println("n " + n + " m " + m);
               //System.out.println("n " + n + " m - 1 " + ( m-1));
               System.out.println("method4: " + count4++);
               primeFactorsR(n, m-1);
            }
      }


    public static void main(String[] args) {  


           primeFactors(20);        

    }
}

出力

n 20 m 19
method4: 1
n 20 m 18
method4: 2
n 20 m 17
method4: 3
n 20 m 16
method4: 4
n 20 m 15
method4: 5
n 20 m 14
method4: 6
n 20 m 13
method4: 7
n 20 m 12
method4: 8
n 20 m 11
method4: 9
n 20 m 10
method2: 1
n 10 m 9
method4: 10
n 10 m 8
method4: 11
n 10 m 7
method4: 12
n 10 m 6
method4: 13
n 10 m 5
method2: 2
5
method1 1
n 10 m 5
method3: 1
2
method1 2
n 20 m 10
method3: 2
2
method1 3
BUILD SUCCESSFUL (total time: 1 second)
4

2 に答える 2

0

再帰呼び出しチェーンを表示するために、コンソール出力にさらに情報を追加しました。
recursionLevel再帰の深さを示します。
各primeFactorsR関数呼び出しは一意のIDを受け取ります（funcId-variableを参照）。
関数IDのシーケンスは、一意の再帰呼び出しパスを作成します- recursionPath。

public class Tester {

    static boolean isPrime(int p) {
        for (int i = 2; i < p; i++) {
            if (p % i == 0) return false;
        }
        return true;
    }

    public static void primeFactors(int n, int recursionLevel) {
        primeFactorsR(n, n - 1, recursionLevel, null);
    }

    static int count1 = 1, count2 = 1, count3 = 1, count4 = 1;
    private static int recursionId = 1;

    public static void primeFactorsR(int n, int m, int recursionLevel, String recursionPath) {
        int funcId = recursionId++;

        if (recursionPath == null)
            recursionPath = String.format("%s", funcId);
        else
            recursionPath = String.format("%s-%s", recursionPath, funcId);

        if (isPrime(n)) {
            System.out.println(String.format("n %s recursionLevel %s recursionPath %s", n, recursionLevel, recursionPath));
            System.out.println("method1 " + count1++);
        } else if (n % m == 0) {
            System.out.println(String.format("n %s m %s recursionLevel %s recursionPath %s", n, m, recursionLevel, recursionPath));
            System.out.println("method2: " + count2++);
            primeFactorsR(m, m - 1, recursionLevel + 1, recursionPath);

            System.out.println(String.format("n %s m %s recursionLevel %s recursionPath %s", n, m, recursionLevel, recursionPath));
            System.out.println("method3: " + count3++);
            primeFactorsR(n / m, (n / m) - 1, recursionLevel + 1, recursionPath);
        } else {
            System.out.println(String.format("n %s m %s recursionLevel %s recursionPath %s", n, m, recursionLevel, recursionPath));
            //System.out.println("n " + n + " m - 1 " + ( m-1));
            System.out.println("method4: " + count4++);
            primeFactorsR(n, m - 1, recursionLevel + 1, recursionPath);
        }
    }

    public static void main(String[] args) {
        primeFactors(20, 1);
    }

}

結果：

n 20 m 19 recursionLevel 1 recursionPath 1
方法4：1
n 20 m 18 recursionLevel 2 recursionPath 1-2
方法4：2
n 20 m 17 recursionLevel 3 recursionPath 1-2-3
方法4：3
n 20 m 16 recursionLevel 4 recursionPath 1-2-3-4
方法4：4
n 20 m15recursionレベル5recursionPath1-2-3-4-5
方法4：5
n 20 m14recursionレベル6recursionPath1-2-3-4-5-6
方法4：6
n 20 m 13 recursionLevel 7 recursionPath 1-2-3-4-5-6-7
方法4：7
n 20 m12recursionレベル8recursionPath1-2-3-4-5-6-7-8
方法4：8
n 20 m11recursionレベル9recursionPath1-2-3-4-5-6-7-8-9
方法4：9
n 20 m 10 recursionLevel 10 recursionPath 1-2-3-4-5-6-7-8-9-10
方法2：1
n 10 m 9 recursionLevel 11 recursionPath 1-2-3-4-5-6-7-8-9-10-11
方法4:10
n 10 m8recursionレベル12recursionPath1-2-3-4-5-6-7-8-9-10-11-12
方法4：11
n 10 m7recursionレベル13recursionPath1-2-3-4-5-6-7-8-9-10-11-12-13
方法4：12
n 10 m6recursionレベル14recursionPath1-2-3-4-5-6-7-8-9-10-11-12-13-14
方法4：13
n 10 m5recursionレベル15recursionPath1-2-3-4-5-6-7-8-9-10-11-12-13-14-15
方法2：2
n5recursionレベル16recursionPath1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16
方法11
n 10 m5recursionレベル15recursionPath1-2-3-4-5-6-7-8-9-10-11-12-13-14-15
方法3：1
n2recursionレベル16recursionPath1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-17
方法12
n 20 m 10 recursionLevel 10 recursionPath 1-2-3-4-5-6-7-8-9-10
方法3：2
n2recursionレベル11recursionPath1-2-3-4-5-6-7-8-9-10-18
方法13

結果から次の行を確認してください。

n 10 m5recursionレベル15recursionPath1-2-3-4-5-6-7-8-9-10-11-12-13-14-15
方法2：2
n5recursionレベル16recursionPath1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16
方法11
n 10 m5recursionレベル15recursionPath1-2-3-4-5-6-7-8-9-10-11-12-13-14-15
方法3：1

ID 15の関数は、ID 16の関数と呼ばれ、次の行を印刷します。

n5recursionレベル16recursionPath1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16

その後、呼び出しは16から15に戻りn、関数15の値はまだ10です。

于 2012-05-23T06:57:46.197 に答える
0

これは、2番目のifステートメントn % m == 0で。を2回呼び出すためprimeFactorsRです。最初の呼び出しは、5が素数であることがわかるスタックの奥深くにあなたを導きます。次に、中断した場所に到達するまでスタックをバックアップし、2番目のprintステートメントに移動して2番目のn 10 m 5を取得します。これは、各レイヤーをインデントし、スタックの深さを出力した出力です。それが最初に入っprimeFactorsRたときとそれが終わったとき。右に向かっているところはスタックの奥深くにあり、上のレイヤーは一時停止しています。レイヤーの処理が完了すると、上のレイヤーに戻ります。そのレイヤーにさらにやることがある場合は、中断したところから続行します。

We are the top layer
n 20 m 19
method4: 1
   We are 1 layers deep
   n 20 m 18
   method4: 2
      We are 2 layers deep
      n 20 m 17
      method4: 3
         We are 3 layers deep
         n 20 m 16
         method4: 4
            We are 4 layers deep
            n 20 m 15
            method4: 5
               We are 5 layers deep
               n 20 m 14
               method4: 6
                  We are 6 layers deep
                  n 20 m 13
                  method4: 7
                     We are 7 layers deep
                     n 20 m 12
                     method4: 8
                        We are 8 layers deep
                        n 20 m 11
                        method4: 9
                           We are 9 layers deep
                           n 20 m 10
                           method2: 1
                              We are 10 layers deep
                              n 10 m 9
                              method4: 10
                                 We are 11 layers deep
                                 n 10 m 8
                                 method4: 11
                                    We are 12 layers deep
                                    n 10 m 7
                                    method4: 12
                                       We are 13 layers deep
                                       n 10 m 6
                                       method4: 13
                                          We are 14 layers deep
                                          n 10 m 5
                                          method2: 2
                                             We are 15 layers deep
                                             Prime 5
                                             method1 1
                                             Finished with layer 15
                                          n 10 m 5
                                          method3: 1
                                             We are 15 layers deep
                                             Prime 2
                                             method1 2
                                             Finished with layer 15
                                          Finished with layer 14
                                       Finished with layer 13
                                    Finished with layer 12
                                 Finished with layer 11
                              Finished with layer 10
                           n 20 m 10
                           method3: 2
                              We are 10 layers deep
                              Prime 2
                              method1 3
                              Finished with layer 10
                           Finished with layer 9
                        Finished with layer 8
                     Finished with layer 7
                  Finished with layer 6
               Finished with layer 5
            Finished with layer 4
         Finished with layer 3
      Finished with layer 2
   Finished with layer 1
Finished
于 2012-05-23T07:00:43.230 に答える