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 */ 

     } 
    } 

} 

然而，有可能有更好的方法来做递归。