在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

您可以通過重載添加f作爲參數，並添加一個私有方法，它可以接受它，並從「主」公共方法調用。

在私有方法，你有三種情況：

1. 停止條款：N == 1：創建一個新的空單
2. ñ％F == 0：遞歸與N'= N/f，f'= f，並將f添加到列表中。
3. n％f！= 0：用n'= n遞歸，f'= f + 1，不要向列表添加任何內容。

代碼：

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

//overlaod 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] 

---

注意：如果你想在上升的因素順序：

1. 開關ArrayList實施，在停止條款（性能問題）
2. 添加具有factors.add(0,f);代替factors.add(f)

Answer 2

你可以通常使用從循環形式到遞歸形式的簡單轉換。通常必須將局部變量移入參數中。通常有兩種形式，一種提供用戶界面，另一種通常是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); 
    } 
} 

注意兩種方法之間的相似性。