一个递归的面试题有答案,可看不懂,请高手解析下原理

Question

一个递归的面试题有答案,可看不懂,请高手解析下原理问题:把一个数组里的数组合全部列出,比如12列出来为1,2,12,21答案:import java.util.*;
import java.io.*;
public class Dg1 {

public static void listAll(List candidate,String prefix) {

System.out.println(prefix);

for(int  i = 0;i < candidate.size();i++)
{
List temp = new LinkedList(candidate);

listAll(temp,prefix + temp.remove(i));
}
}

public static void main(String[] args) {
String[] array = new String[] {
"1","2"
};

listAll(Arrays.asList(array),"");
}
}

Answer 1

public   static   void   listAll(List   candidate,String   prefix)   { System.out.println(prefix); for(int     i   =   0;i   <   candidate.size();i++) 
{ 
List   temp   =   new   LinkedList(candidate); listAll(temp,prefix   +   temp.remove(i)); 
} 
} 
－－－－－－－－－－－－－－－－－－－－－－
先将原来的数组进行转换，转换成链表
对此链表进行循环处理操作，每次循环有一个位置（这个位置是取出来数的位置）
利用中间链接对原链表进行打印处理
－－－－－－－－－－－－－－－－－－－－－－   candidate = 1->2
第一次：
temp = 1->2 除去第i个位置的数，这里是0位置的数，也就是1 
循环temp.size()也就是两次
调用递归函数，打印刚移去的数：1，再调用一次，此时移去的是2，加上上次移去的1，此次打印的是12
第二次：
temp = 1->2 除去第i个位置的数，这里是1位置的数，也就是2
循环temp.size()也就是两次
调用递归函数，打印刚移去的数：2，再调用一次，此时移去的是1，加上上次移去的2，此次打印的是21
   

Answer 2

....加了几个程序路径记录....看递归程序..多加些辅助输出挺好的
import   java.util.*; 
import   java.io.*; 
public   class   Dg1   { public   static   void   listAll(List   candidate,String   prefix)   { System.out.println("prefix = "+prefix); for(int     i   =   0;i   <   candidate.size();i++) 
{ 
List   temp   =   new   LinkedList(candidate); 
System.out.println("temp= "+temp.toString());
String str=(String)temp.remove(i);
System.out.println("temp.remove("+i+") ="+str);
listAll(temp,prefix   +   str); 
} 
} public   static   void   main(String[]   args)   { 
String[]   array   =   new   String[]   { 
"1","2" 
}; 
System.out.println(Arrays.asList(array).toString());
listAll(Arrays.asList(array),""); } 
} 

Answer 3

  candidate   =   1-> 2 
第一次： 
temp   =   1-> 2   除去第i个位置的数，这里是0位置的数，也就是1   
循环temp.size()也就是两次 
调用递归函数，打印刚移去的数：1，再调用一次，此时移去的是2，加上上次移去的1，此次打印的是12 
第二次： 
temp   =   1-> 2   除去第i个位置的数，这里是1位置的数，也就是2 
循环temp.size()也就是两次 
调用递归函数，打印刚移去的数：2，再调用一次，此时移去的是1，加上上次移去的2，此次打印的是21 
      

Answer 4

System.out.println("prefix   =   "+prefix);   for(int           i       =       0;i       <       candidate.size();i++)   
{   
List       temp       =       new       LinkedList(candidate);   
System.out.println("temp=   "+temp.toString()); 
String   str=(String)temp.remove(i); 
System.out.println("temp.remove("+i+")   ="+str); 
listAll(temp,prefix       +       str);   
}   
System.out.println("aaaaaaaaaaa");
}   
  
还有个问题,最后一次输出 aaaaaaaaaaa     是三次  而不是两次呢?

Answer 5

大家都搞清楚了，不过我还是想把我的分析列一下，看看与你们的分析是否一样？
关于递归函数调用的问题，我想我们要先搞清楚“调用栈”问题，什么是“调用栈”呢？
我的理解是，递归之前，系统会保存当前CPU栈上的所有内容，如何保存呢？当然是入栈了，在这理我想我们对于数据结构中的“栈”应该都不陌生的。调用完成之后呢，就是出栈了，其实总结一下就是一句话：调用之前入栈，调用完成后出栈。
好的，有了理论后，我们来分析一下具体执行程序时，系统是如何做的？
在这理，为了理解方便，我们将当前栈上的数据都列一下：
1.main中的listAll()被调用，
此时，栈上的内容是:array(1,2),prefix=""
listAll方法中，println(prefix)执行，输出=>""
此时，栈顶的内容是：
prefix="";
candidate="1,2"
for()开始执行=>i=0;candidate.size() = 2
执行new LinkedList后，temp的值如下：
temp = 1->2;
调用listAll()=>
temp=> 2;
temp_prefix => prefix + "1";--为什么会多出个temp_prefix呢，因为，我们使用了prefix+temp.remove(i)时，
编译器会自动为我们生成一个临时的String对象来存储prefix+temp.remove(i)的值
好的，递归前，系统会将这些变量入栈：
①：
i=>0;
temp=>2
prefix=>""
candidate=>"1,2"递归调用listAll(temp,prefix)，此时：
candidate=>"2"
prefix=>"1",println(prefix)输出1进入for()
i=0;
candidate.size() = 1;
i < candidate.size() == true，条件成立,执行:temp = new LinkedList(candidate) =>temp="2"
listAll()调用,调用的参数内容如下：
temp=>""
temp_prefix= prefix + temp.remove(0) ==> "1" + "2"
系统同样将当前栈上的内容入栈，以下是当前栈上的内容
②：
i=0
candidate=>2
prefix="1"
temp=>""递归进来后，此时栈的内容如下：
candidate=""
prefix="12";
print(prefix)后，输出"12"
好的，开始执行for()
i=0;candidate.size() = 0;条件不成立，没有进入for内，此函数已经没有要执行的下一条语句，结束调用，
开始出栈，到此，我们的栈内只有两项栈记录，出栈时，首先弹出②，此时我们看一下
栈②内容：
i=0
candidate=>2
prefix="1"
temp=>""
现在系统执行for()->
i++ => i=1; candidate.size()=1 
条件:i < candidate.size() == false，不执行
结束调用，出栈，此时弹出①栈，好的，我们看一下，栈①的内容：
①：
i=>0;
temp=>2
prefix=>""
candidate=>"1,2"执行for()
i++ => i=1;
candidate.size() = 2;
条件:i < candidate.size() == true，执行
temp = new LinkedList(candidate) => temp = 1->2;
调用:listAll(temp,prefix + temp.remove(i)) =>此时，参数值如下：
i = 1;
temp=> 1;
temp_prefix = "" + "2";
保存栈内容：
③：
candidate="1,2";
i = 1;
temp => 1;
prefix="";递归listAll("1","2"),
执行print(prefix)，输出 2
我们看一下当前栈上的内容：
i=0;
candidate="1";
prefix="2"
执行for()
i=0; candidate.size() = 1;
条件i < candidate.size() == true，执行
temp = new LinkedList(candidate);
temp=>"1";
调用listAll(temp,prefix);
temp=> "";
temp_prefix = "2" + temp.remove(0) ==> temp_prefix="21"
此时，保存当前栈内容：
④：
candidate="1";
temp="";
i=0;
prefix="2";调用listAll("","21");
println(prefix)输出"21"
i=0;
candidate="";
i < candidate.size() == false，条件不成立，返回，出栈，首先弹出的是栈④，我们看一下栈④的内容：
④：
candidate="1";
temp="";
i=0;
prefix="2";
此时，开始执行for()
i++ => i=1; candidate.size() == 1;
i < candidate.szie() == false，条件不成立，返回，出栈，此时弹出的是栈③，我们看一下栈③的内容：
③：
candidate="1,2";
i = 1;
temp => 1;
prefix="";
执行for();
i++ => i= 2;
candidate.size() = 2;
i < cnadidate.size() == false，条件不成立，返回，出栈，此时弹出的是main函数在调用listAll()之前 的栈，
如此，整个递归执行完毕，输出的内容：
""
1
12
2
21

Answer 6

大家都搞清楚了，不过我还是想把我的分析列一下，看看与你们的分析是否一样？ 
关于递归函数调用的问题，我想我们要先搞清楚“调用栈”问题，什么是“调用栈”呢？ 
我的理解是，递归之前，系统会保存当前CPU栈上的所有内容，如何保存呢？当然是入栈了，在这理我想我们对于数据结构中的“栈”应该都不陌生的。调用完成之后呢，就是出栈了，其实总结一下就是一句话：调用之前入栈，调用完成后出栈。 
好的，有了理论后，我们来分析一下具体执行程序时，系统是如何做的？ 
在这理，为了理解方便，我们将当前栈上的数据都列一下： 
1.main中的listAll()被调用， 
此时，栈上的内容是:array(1,2),prefix="" 
listAll方法中，println(prefix)执行，输出=> "" 
此时，栈顶的内容是： 
prefix=""; 
candidate="1,2" 
for()开始执行=> i=0;candidate.size()   =   2 
执行new   LinkedList后，temp的值如下： 
temp   =   1-> 2; 
调用listAll()=> 
temp=>   2;                            这一步为什么temp为2了
temp_prefix   =>   prefix   +   "1";--为什么会多出个temp_prefix呢，因为，我们使用了prefix+temp.remove(i)时， 
编译器会自动为我们生成一个临时的String对象来存储prefix+temp.remove(i)的值 
好的，递归前，系统会将这些变量入栈： 
①： 
i=> 0; 
temp=> 2 
prefix=> "" 
candidate=> "1,2" 递归调用listAll(temp,prefix)，此时： 
candidate=> "2" 
prefix=> "1",println(prefix)输出1 进入for() 
i=0; 
candidate.size()   =   1; 
i   <   candidate.size()   ==   true，条件成立,执行: temp   =   new   LinkedList(candidate)   => temp="2" 
listAll()调用,调用的参数内容如下： 
temp=> "" 
temp_prefix=   prefix   +   temp.remove(0)   ==>   "1"   +   "2" 
系统同样将当前栈上的内容入栈，以下是当前栈上的内容 
②： 
i=0 
candidate=> 2 
prefix="1" 
temp=> "" 递归进来后，此时栈的内容如下： 
candidate="" 
prefix="12"; 
print(prefix)后，输出"12" 
好的，开始执行for() 
i=0;candidate.size()   =   0;条件不成立，没有进入for内，此函数已经没有要执行的下一条语句，结束调用， 
开始出栈，到此，我们的栈内只有两项栈记录，出栈时，首先弹出②，此时我们看一下 
栈②内容： 
i=0 
candidate=> 2 
prefix="1" 
temp=> "" 
现在系统执行for()-> 
i++   =>   i=1;   candidate.size()=1   
条件:i   <   candidate.size()   ==   false，不执行 
结束调用，出栈，此时弹出①栈，好的，我们看一下，栈①的内容： 
①： 
i=> 0; 
temp=> 2 
prefix=> "" 
candidate=> "1,2"执行for() 
i++   =>   i=1; 
candidate.size()   =   2; 
条件:i   <   candidate.size()   ==   true，执行 
temp   =   new   LinkedList(candidate)   =>   temp   =   1-> 2; 
调用:listAll(temp,prefix   +   temp.remove(i))   => 此时，参数值如下： 
i   =   1; 
temp=>   1; 
temp_prefix   =   ""   +   "2"; 
保存栈内容： 
③： 
candidate="1,2"; 
i   =   1; 
temp   =>   1; 
prefix=""; 递归listAll("1","2"), 
执行print(prefix)，输出   2 
我们看一下当前栈上的内容： 
i=0; 
candidate="1"; 
prefix="2" 
执行for() 
i=0;   candidate.size()   =   1; 
条件i   <   candidate.size()   ==   true，执行 
temp   =   new   LinkedList(candidate); 
temp=> "1"; 
调用listAll(temp,prefix); 
temp=>   ""; 
temp_prefix   =   "2"   +   temp.remove(0)   ==>   temp_prefix="21" 
此时，保存当前栈内容： 
④： 
candidate="1"; 
temp=""; 
i=0; 
prefix="2"; 调用listAll("","21"); 
println(prefix)输出"21" 
i=0; 
candidate=""; 
i   <   candidate.size()   ==   false，条件不成立，返回，出栈，首先弹出的是栈④，我们看一下栈④的内容： 
④： 
candidate="1"; 
temp=""; 
i=0; 
prefix="2"; 
此时，开始执行for() 
i++   =>   i=1;   candidate.size()   ==   1; 
i   <   candidate.szie()   ==   false，条件不成立，返回，出栈，此时弹出的是栈③，我们看一下栈③的内容： 
③： 
candidate="1,2"; 
i   =   1; 
temp   =>   1; 
prefix=""; 
执行for(); 
i++   =>   i=   2; 
candidate.size()   =   2; 
i   <   cnadidate.size()   ==   false，条件不成立，返回，出栈，此时弹出的是main函数在调用listAll()之前   的栈， 
如此，整个递归执行完毕，输出的内容： 
"" 
1 
12 
2 
21 

Answer 7

呵呵..上面是偶在CSDN发的第一个帖..客气了..LZ..

Answer 8

1.main中的listAll()被调用，   
此时，栈上的内容是:array(1,2),prefix=""   
listAll方法中，println(prefix)执行，输出=>   ""   
此时，栈顶的内容是：   
prefix="";   
candidate="1,2"   
for()开始执行=>   i=0;candidate.size()       =       2   
执行new       LinkedList后，temp的值如下：   
temp       =       1->   2;   
调用listAll()=>   
temp=>       2;                                                         这一步为什么temp为2了 因为调用temp.remove(i)后，此时，i=0;此时temp中的第0个元素已经被removed了，所以，temp中就只有2这个元素了

Answer 9

到了i=1的时候。prefix怎么值为空了。 
在i=0里prefix的值还为1  , 然后在加为12.

Answer 10

到了i=1的时候。prefix怎么值为空了。  
在i=0里prefix的值还为1     ,   然后在加为12. 
因为，此时的内容是栈①的内容，