Java遞歸例程疑問

Question

我實現了一個遞歸例程來計算多項式表達式的所有項，基本上是一個多項式展開式。我認爲這可以轉化爲以下幾條問題： -

給定一組值爲[0,1,2，... n]的n個數組是多少這可以實現k的總和。

以下是遞歸例程 -

public static String []multinomial_elements; 
public static void multichoose(int n,int k) 
{ 
    String[] result = null; 
    System.out.print("Calling multichoose with"); 
    System.out.println(" "+Integer.toString(n)+" "+Integer.toString(k)); 
    if(n==1) 
    { 
     multinomial_elements[result_iter]=multinomial_elements[result_iter]+Integer.toString(k)+"|"; 
     ++result_iter; 
    } 
    else 
    { 
     if(k==0) 
     { 
      result=new String[1]; 
      result[0]="0"; 
      for(int a=0;a<n;a++) 
       multinomial_elements[result_iter]=multinomial_elements[result_iter]+"0"+"|"; 
      ++result_iter; 
     } 
     else 
     { 
      for(int firstindexval=k;firstindexval>=0;firstindexval--) 
       for(int iter=0;iter<=k-firstindexval;iter++) 
       { 
        if(iter+firstindexval==k){ 

         multinomial_elements[result_iter]=multinomial_elements[result_iter]+Integer.toString(firstindexval)+"|"; 

         multichoose(n-1,iter); 
        } 

       } 

     } 
    } 

} 

multinomial_elements如果將包含1個條目來回膨脹的每個術語陣列。上述代碼背後的基本思想是，從第一項的最大可能值（功率），我迭代到它的最低可能值（功率），並且通過這樣做遞歸地對其他項應用相同的邏輯。 從表示函數調用的打印語句中，我能夠推斷出我能夠以正確的方式看到Im遍歷樹。然而輸出看起來不穩定。我似乎在將'firstindexval'添加到數組multinomial_terms的地方搞亂了。這似乎發生在Im在處理較低節點之後返回到較高節點並因此程序不再具有「firstindexval」意義的情況下發生。這個推論是基於如下輸出 -

multichoose(3, 3); 

3|0|0| 
2|1|0| 
0|1| 
1|2|0| 
1|1| 
0|2| 
0|3|0| 
2|1| 
1|2| 
0|3| 

任何指針或提示我什麼我做錯了會有很大的幫助。

感謝 p1ng

Answer 1

您日常的意圖似乎是，給定一個總和k和總數方面n的，發現有0之間填充n條款與值的所有排列和包括k。我假設這將意味着，對於情況n=3, k=3，你正在尋找

3|0|0| 
2|0|1| 
2|1|0| 
1|0|2| 
1|1|1| 
1|2|0| 
0|0|3| 
0|1|2| 
0|2|1| 
0|3|0| 

你的代碼是有點雜亂無章但是。特別是，循環for(int iter=0;iter<=k-firstindexval;iter++)是完全不必要的，因爲它內部的if語句，可以通過遞歸調用中的k直接聲明爲k - firstindexval來取代。程序內部與方法變量String[] result相關的所有代碼也似乎完全沒有必要。

你的代碼的主要問題是它返回void，並且遞歸調用不會傳遞遞歸的當前狀態 - 換句話說，你沒有直接或間接地使用堆棧，這使得它非常困難在遍歷遞歸樹時記住解決方案的當前狀態。

例如，在2|1|0|後你的問題，你的下一個結果爲0|1|正確2|0|1|，而不是因爲遞歸不知道如何早先的狀態2|追加到數組中的答案，即「堆狀態」沒有維護在生成的答案中。

使代碼正常工作的一個快速方法是向multichoose添加一個額外的String參數，該參數包含遞歸的狀態，如下所示。我已經添加到您的代碼的評論解釋了這些更改。

public static void multichoose(int n,int k, String currentSolution /* NEW ARGUMENT */) 
{ 
    // String[] result = null; /* UNNECESSARY */ 
    System.out.print("Calling multichoose with"); 
    System.out.println(" "+Integer.toString(n)+" "+Integer.toString(k)); 
    if(n==1) 
    { 
     // multinomial_elements[result_iter]=multinomial_elements[result_iter]+Integer.toString(k)+"|"; 
     multinomial_elements[result_iter]=currentSolution+k+"|"; /* CHANGED */ 
     ++result_iter; 
    } 
    else 
    { 
     if(k==0) 
     { 
      // result=new String[1]; /* UNNECESSARY */ 
      // result[0]="0"; /* UNNECESSARY */ 
      for(int a=0;a<n;a++) 
       // multinomial_elements[result_iter]=multinomial_elements[result_iter]+"0"+"|"; 
       currentSolution += "0|"; /* CHANGED */ 
      multinomial_elements[result_iter] = currentSolution; /* NEW */ 
      ++result_iter; 
     } 
     else 
     { 
      for(int firstindexval=k;firstindexval>=0;firstindexval--) 
       //for(int iter=0;iter<=k-firstindexval;iter++) /* UNNECESSARY */ 
       //{ /* UNNECESSARY */ 
        //if(iter+firstindexval==k){ /* UNNECESSARY */ 

         //multinomial_elements[result_iter]=multinomial_elements[result_iter]+Integer.toString(firstindexval)+"|"; /* SEE CHANGE BELOW */ 

         //multichoose(n-1,iter); 
         multichoose(n-1, k-firstindexval /* CHANGED */, currentSolution+firstindexval+"|" /* NEW ARGUMENT */); /* CHANGED */ 
        //} /* UNNECESSARY */ 

       //} /* UNNECESSARY */ 

     } 
    } 

} 

然而，有可能有更好的方法來做遞歸。