recursion - Java recursive routine doubt -

im implementing recursive routine calculate terms of multinomial expression, multinomial expansion. kind of figured translates a problem along following lines --

given set of n numbers values ranging [0,1,2,...n] maximum number of combinations sum of k can achieved.

the following recursive routine --

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 if array contain 1 entry fro every term of expansion. basic idea behind above code maximum possible value(power) of first term, iterate lowest possible value(power) , doing apply same logic on other terms recursively. print statements denoting function call, im able infer able see im traversing tree in right manner. output seems erratic. seem messing in place im adding 'firstindexval' array multinomial_terms. seems happen in cases wherein im returning higher node after processing lower node , hence program no longer has sense of 'firstindexval'. inference based on output below --

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| 

any pointers or hints on doing wrong of great help.

thanks p1ng

the intent of routine seems that, given sum total of k , total number of terms n, find permutations of populating n terms values between 0 , k inclusive. i'm assuming mean case n=3, k=3, you're looking for

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| 

your code bit haphazard however. in particular, loop for(int iter=0;iter<=k-firstindexval;iter++) unnecessary given if statement inside it, , can replaced directly declaring k in recursive call k - firstindexval. code inside routine related method variable string[] result seems unnecessary.

the main problem code returns void, , recursive calls not pass current state of recursion - in other words, you're not making using of stack directly or indirectly, makes difficult remember current state of solution while you're traversing recursive tree.

for example, in question after 2|1|0|, next result 0|1| instead of correct 2|0|1| because recursion did not know how append earlier state 2| answers in array, i.e. "stack state" not maintained in generated answers.

one quick way code work add additional string argument multichoose contains state of recursion, below. comments i've added code explains changes.

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

there better ways recursion however.