java中的递归求几个数字的排列组合

Question

public class Test5 {
public static void main(String[] args) {

     List<Integer> s=new ArrayList<Integer>();  
     List<Integer> rs=new ArrayList<Integer>();  
     for(int i=1;i<=4;i++)  
         s.add(i);  
     pl(s,rs);  

}

public static void pl(List s,List rs){

   if(s.size()==1)  
   {  

       rs.add(s.get(0));  
       System.out.println(rs.toString());  
       rs.remove(rs.size()-1);  

   }else{  

       for(int i=0;i<s.size();i++){  

           rs.add(s.get(i));   
           List<Integer> tmp=new ArrayList<Integer>();  
           for(Integer a:s)  
              tmp.add(a);  
           tmp.remove(i);  
          pl(tmp,rs);  
          rs.remove(rs.size()-1);      

       }  
   }                     

}

}

 求大神问一下这段递归是什么意思？，新人表示看不懂

Answer 1

深度优先遍历思想：
for(int ...)
每次从当前剩下的可选数字中选出一个

for(Integer ...)
tmp.add()
tmp.remove
用于挑选出剩下的还未被挑选的数字
pl(tmp, rs)
递归选择下一个数字
rs.remove(rs.size()-1)
rs添加s.get(i)的情况结束，移除最后选择的数字，以运行循环选择另一个不同的数字

说实话这递归写的不怎么样啊，开销很大，逻辑不够清晰。
我写的一个递归解法如下：

public class Sort
{
public static void main(String[] args)
{
int size = 4;
int[] result = new int[size];
int[] status = new int[size];
for(int i = 0; i < size; i++)
{
result[i] = 0;
status[i] = 0;
}
int expect = 1;
for(int i = 2; i <= size; i++)
{
expect *= i;
}
System.out.println("Expect total = "+expect);
int total = sort(result, status, 0);
System.out.println("Real total="+total);
}

/**
* find an available element in status array to fill result[index].
* If index == status.length, result array has been completely filled.So, just print it.
* status[i]=0 means that i is available, status[i]=1 means that i has been used.
*/
public static int sort(int[] result, int[] status, int index)
{
    int total = 0;
    int len = status.length;
    //result has been completely filled, print the array
    if(index >= len)
    {
        for(int i = 0; i < len; i++)
            System.out.print(result[i]+" ");
        System.out.println();
        return 1;
    }
    //find an avaliable element
    for(int i = 0; i < len; i++)
    {
        //select an available element
        if(status[i] != 1)
        {
            result[index] = i;
            status[i] = 1;
            //select the next element whose index is (index+1)
            total += sort(result, status, index+1);
            //finish selected the element whose index is (index+!), release i
            status[i] = 0;
        }
    }
    return total;
}

}