0

我有以下方法，在这种情况下显示数字的所有素数 20。我了解该方法的大部分递归行为，但是在打印数字 5 后我有点困惑，为什么 n 回到 10上一次调用时为5时（即执行第三个递归方法时）

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-function 调用都会收到唯一的 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 m 15 recursionLevel 5 recursionPath 1-2-3-4-5
方法4：5
n 20 m 14 recursionLevel 6 recursionPath 1-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 m 12 recursionLevel 8 recursionPath 1-2-3-4-5-6-7-8
方法4：8
n 20 m 11 recursionLevel 9 recursionPath 1-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 m 8 recursionLevel 12 recursionPath 1-2-3-4-5-6-7-8-9-10-11-12
方法4：11
n 10 m 7 recursionLevel 13 recursionPath 1-2-3-4-5-6-7-8-9-10-11-12-13
方法4：12
n 10 m 6 recursionLevel 14 recursionPath 1-2-3-4-5-6-7-8-9-10-11-12-13-14
方法4：13
n 10 m 5 recursionLevel 15 recursionPath 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15
方法2：2
n 5 recursionLevel 16 recursionPath 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16
方法1 1
n 10 m 5 recursionLevel 15 recursionPath 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15
方法3：1
n 2 recursionLevel 16 recursionPath 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-17
方法1 2
n 20 m 10 recursionLevel 10 recursionPath 1-2-3-4-5-6-7-8-9-10
方法3：2
n 2 recursionLevel 11 recursionPath 1-2-3-4-5-6-7-8-9-10-18
方法1 3

从结果中检查这一行：

n 10 m 5 recursionLevel 15 recursionPath 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15
方法2：2
n 5 recursionLevel 16 recursionPath 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16
方法1 1
n 10 m 5 recursionLevel 15 recursionPath 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15
方法3：1

ID 为 15 的函数，调用 ID 为 16 的函数，打印行：

n 5 recursionLevel 16 recursionPath 1-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

这是因为在您的第二个 if 语句中n % m == 0，它两次调用primeFactorsR. 第一个调用将您带入更深的堆栈，结果表明 5 是素数。然后它返回堆栈直到它到达它离开的地方并移动第二个打印语句，给你第二个 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 回答