遞歸與Java的因式分解處理StackOverflow

我需要編寫一個遞歸地將數字因素分解爲1234567890的方法，我的當前應用程序在拋出StackOverflowError之前只能處理很小的數字。我知道我的問題是遞歸調用太多，但我無法弄清楚如何減少我的電話數量。遞歸與Java的因式分解處理StackOverflow

它需要遞歸。

我在想這個解決方案與算法背後的數學有關。我看過不同的迭代解決方案，我似乎無法用少量調用遞歸地執行它。代碼：

public static boolean isPrime(int input, int i) { 
    if (i <= 2) { 
     return true; 
    } 
    if (input % i != 0) { 
     return isPrime(input, i-1); 
    } else { 
     factors(input, i); 
     return false; 
    } 
} 
public static void factors(int input, int i) { 
    if (i <= 1) { 
     System.out.printf(" %d", 1); 
    } else { 
     if (input % i == 0) { 
      System.out.printf(" %d", i); 
     } 
     factors(input, i - 1); 
    } 
}

，並開始由：

System.out.println("What integer would you like to factor?"); 
    num1 = scan.nextInt(); 
    if(isPrime(num1, num1 - 1)){ 
     System.out.println("Input is a prime number"); 
    } else { 
     System.out.println(" factors\nInput isn't a prime number."); 
    }

來源

2013-04-14 user2272115

你如何開始這種方法？你能提供一些例子嗎？你必須使用遞歸，因爲這可以在沒有遞歸的情況下完成。我建議你展示使用實際的代碼，因爲這仍然不會編譯。 –

我添加了它使用的部分，它也應該可以工作。它必須是遞歸的。 – user2272115

嘗試改爲'isPrime（num1，（int）Math.sqrt（num1））'它將具有N^0.5而不是N的深度。如果您願意，可以將'i'和'n/i'都打印出來需要兩個。 –

我認爲它需要遞歸的原因是因爲這是一個作業問題。所以我不會告訴你如何去做，而是你的數學有什麼問題。你的算法看起來部分是正確的，除了（a）你忘記按你找到的每個因子劃分'n'，並且（b）你正在尋找大數而不是小數的因子。最好開始2，然後數到sqrt（n），儘管這不會解決堆棧溢出問題。

您需要在循環中查找因子，並保留使用遞歸（如果您真的需要使用它），以在劃分素因子後對剩餘數進行因式分解。因爲你不想通過一個6位數的素數，然後需要100萬級的堆棧來證明它沒有任何因素。即，這需要在簡單的循環中而不是遞歸：

return isPrime（input，i-1）;

...並且這可以是遞歸的：

factors（input，i）;

來源

2013-04-14 10:22:10

在Java增加堆棧大小。你可以搜索如何增加堆棧大小

來源

2013-04-14 09:27:35 aymankoo

改變你的因子方法是非遞歸（如果它不被遞歸要求）

public static void factors(int input, int i) { 
    for(int j = i; j >= 1; j--) { 
     if (input % j == 0) 
      System.out.println(j); 
    } 
}

編輯：類似下面是一個遞歸解決這個問題的方法。

public void isPrime(int num1) 
{ 
int count=countFactors(num1); 
if(count==0) 
System.out.println("No is prime"); 
} 

public int countFactors(int num,int i) 
{ 

if(i>num/2)return 0; 
if(num%i==0) 
{ 
System.out.println(i); 
return 1+countFactors(num,i+1); 
} 

}

來源

2013-04-14 09:33:27 Algorithmist

它必須是遞歸的。 – user2272115

在這種情況下，您當前的邏輯是完全錯誤的。 – Algorithmist

我的邏輯錯誤是怎麼回事？它適用於較小的數字。在尋找因素方面還是在執行遞歸方面？ – user2272115

您似乎用於素性檢查的算法是trial division algorithm。

有一些other methods，但是，保持這一戰略，有一個命題，說明你只需要檢查到平方根ñ，其中ñ是你input。此外，您的謂詞不會適當地處理負整數（返回true）。

因此，在第一種方法，你的算法是：

public static boolean isPrime(int n) { 
    if (n < 2) { return false; } 
    return helper_isPrime(n, 2, (int) Math.sqrt(n)); 
}

其中：

private static boolean helper_isPrime(int n, int i, int max) { 
    if (i > max) { return true; } 
    if (n % i == 0) { return false; } 
    return helper_isPrime(n, i+1, max); 
}

在分離兩種方法分離株n < 2測試。請注意，n將保持不變，因此測試只需在進程開始時執行一次。

此外，保理被留下。在我看來，這應該問從外面看，像這樣：

System.out.println("What integer would you like to factor?"); 
num1 = scan.nextInt(); 
if(isPrime(num1)){ 
    System.out.println("Input is a prime number"); 
} else { 
    System.out.println("Input isn't a prime number."); 
    int[] fac = factor(n); 
    System.out.println("Factors: " + fac.toString()); 
}

凡factor將是你最喜歡的因素算法。一個分解算法可能會發現它是使用素數執行的最糟糕的情況，但是，由於已經進行了測試，並且由於只有在數字不是素數時纔會調用該算法，因此不會發生這種情況。

來源

2013-04-14 10:34:22 afsantos

您可以使用尾部調用優化技術（包括Java不爲你做什麼）與

public static void factors(int input, int i) { 
    while(i > 1) { 
     if (input % i == 0) { 
      System.out.printf(" %d", i); 
     } 
     i = i - 1; 
    } 
    System.out.printf(" %d", 1); 
}

當然除了你不再做遞歸。

來源

2013-04-14 10:38:25

遞歸與Java的因式分解處理StackOverflow

回答

相關問題