在 Java 中使用递归的质因数

Question

我在 java 中遇到递归问题。所以我有下面的方法，我应该只用递归而不是任何循环来转换它。

public static List<Integer> primesLoop(int n) {
    List<Integer> factors = new ArrayList<Integer>();
    int f = 2;
    while (f <= n)
        if (n % f == 0) {
            factors.add(f);
            n /= f;
        } else
            f++;
    return factors;
}

递归方法应该以相同的形式开始：

public static List<Integer> primesRec(int n);

而且我应该为转换定义帮助方法结果例如：

primesRec(900) -> prime factors of 900 : [2, 2, 3, 3, 5, 5]

Answer 1

您通常可以使用从循环形式到递归形式的简单转换。局部变量通常必须移动到参数中。通常有两种形式，一种提供用户界面，另一种通常 private 实际上执行递归功能。

public static List<Integer> primesLoop(int n) {
    List<Integer> factors = new ArrayList<Integer>();
    int f = 2;
    while (f <= n) {
        if (n % f == 0) {
            factors.add(f);
            n /= f;
        } else {
            f++;
        }
    }
    return factors;
}

public static List<Integer> primesRecursive(int n) {
    // The creation of factors and the start at 2 happen here.
    return primesRecursive(new ArrayList<>(), n, 2);
}

private static List<Integer> primesRecursive(ArrayList<Integer> factors, int n, int f) {
    // The while becomes an if
    if (f <= n) {
        // This logic could be tuned but I've left it as-is to show it still holds.
        if (n % f == 0) {
            factors.add(f);
            // Make sure either n ...
            n /= f;
        } else {
            // ... or f changes to ensure no infinite recursion.
            f++;
        }
        // And we tail-recurse.
        primesRecursive(factors, n, f);
    }
    return factors;
}

public void test() {
    for (int n = 10; n < 100; n++) {
        List<Integer> loop = primesLoop(n);
        List<Integer> recursive = primesRecursive(n);
        System.out.println("Loop     : " + loop);
        System.out.println("Recursive: " + recursive);
    }
}

注意这两种方法之间的相似性。

Answer 2

您可以通过重载添加 f 作为参数，并添加接受它并从 "main" public 方法调用的私有方法。

在私有方法中，你有3种情况：

停止子句：n==1：创建一个新的空列表
n%f == 0：递归n'=n/f，f'=f，将f添加到列表中。
n%f != 0: 递归 n'=n，f'=f+1，不要向列表中添加任何内容。

代码：

public static List<Integer> primesRecursive(int n) {
    return primesRecursive(n, 2);
 }

 //overload a private method that also takes f as argument:
 private static List<Integer> primesRecursive(int n, int f) {
     if (n == 1) return new ArrayList<Integer>();
     if (n % f == 0) {
         List<Integer> factors = primesRecursive(n/f, f);
         factors.add(f);
         return factors;
     } else
         return primesRecursive(n, f+1);
 }

正如预期的那样，调用：

public static void main(String args[]) {
    System.out.println(primesRecursive(900));
}

将产生：

[5, 5, 3, 3, 2, 2]

注意：如果您希望因素升序排列：

在停止子句中将 ArrayList 实现切换为 LinkedList（针对性能问题）
用 factors.add(0, f); 添加项目而不是 factors.add(f)

在 Java 中使用递归的质因数

Prime factors using recursion in Java

java

algorithm

recursion

primes

prime-factoring