黑马程序员技术交流社区

标题: 有个递归没搞懂 [打印本页]
作者: 清心玉质    时间: 2015-9-24 23:54
标题: 有个递归没搞懂
getString（）这个递归方法，复制了集合进行移除 再将移除后的集合作为参数传给此方法。我不明白的是 在i=0移除完后怎么还有不空集合传进去呢，还是我哪里理解错了，望高手指教

private static void combinations(String st,String s) {
                //将输入的字符串转化为字符数组，并定义集合用于存储字符元素
                ArrayList<Character> al =new ArrayList<Character>();
                char[] ch = s.toCharArray();
                //遍历字符数组，并将元素添加到集合
                for(char c:ch)
                {
                        al.add(c);
                }
                //调用getString()方法 并将集合与字符串传给方法
                getString(al,st);
        }
        
        private static void getString(ArrayList<Character> al,String prefix)
        {
                        
                for(int index=0;index<al.size();index++)
                {      //复制集合                           
                        ArrayList<Character> alCopy = new ArrayList<Character>();
                        alCopy.addAll(al);
                        String str=prefix+alCopy.get(index);
                        //移除复制集合中的元素
                        alCopy.remove(index);
                       //递归调用本方法
                        getString(alCopy,str);
                }
        }


作者: fmi110    时间: 2015-9-24 23:54
你的代码看的好废力啊    我觉的你把递归和循环同时混到一起用了
我猜 你想实现的功能是：   把集合的字符，拼接成一个字符串
如果这样的话你的代码明显有问题。要实现这个功能首先一定要遍历整个集合才能实现。
第一种方法：for循环     for(int index=0;index<al.size();index++)  这个循环就已经实现遍历了，你每次递归再循环，肯定是多此一举的
第二种方法：递归实现   每次递归时，删除一个字符，重复，直到集合的长度变为0时，结束。每次递归只是需要删除一个字符（删除字符这个动作是影响到递归次数的，拼接字符当做不相干的动作），所以递归是用不到循环的。
此外，递归和循环是可以实现转换的。基于“把集合的字符，拼接成一个字符串”这个功能，我把递归和等效的循环写了代码如下，一起交流哈，不对的指正
  1. import java.util.ArrayList;

  3. public class T4 {
  4.         static int i = 0;
  5.         public static void main(String[] args) {
  6.                 ArrayList<Character> al = new ArrayList<Character>();
  7.                 al.add('a');
  8.                 al.add('b');
  9.                 al.add('c');
  10.                 String str = "";
  11. //                getString(al,str);
  12.                 getString1(al,str);
  13.         }
  14.         //递归实现“把集合的字符，拼接成一个字符串”
  15.         private static void getString(ArrayList<Character> al, String prefix) {
  16.                 System.out.println("第"+(++i)+"次递归，操作前的集合为"+al);
  17.                 prefix = prefix + al.remove(0); //递归的动作：将集合的元素拼接到字符串后面，并将已拼接的字符移除
  18.                 System.out.println("字符串为："+prefix);
  19.                 if (al.size() > 0) {//可以进行递归的条件是集合的长度大于0
  20.                         getString(al, prefix);
  21.                 }
  22.         }
  23.         //循环实现“把集合的字符，拼接成一个字符串”
  24.         private static void getString1(ArrayList<Character> al, String prefix) {
  25.                 for(;al.size()>0;){//循环结束的条件是集合长度为0
  26.                         System.out.println("第"+(++i)+"次循环，操作前的集合为"+al);
  27.                         prefix = prefix + al.remove(0); //递归的动作：将集合的元素拼接到字符串后面，并将已拼接的字符移除
  28.                         System.out.println("字符串为："+prefix);
  29.                 }
  30.                 System.out.println("for循环结束后，字符串为"+prefix+"  集合为："+al);
  31.        
  32.         }
  33. }

  35. 递归函数运行的结果：
  36. 第1次递归，操作前的集合为[a, b, c]
  37. 字符串为：a
  38. 第2次递归，操作前的集合为[b, c]
  39. 字符串为：ab
  40. 第3次递归，操作前的集合为[c]
  41. 字符串为：abc

  43. 循环的输出
  44. 第1次循环，操作前的集合为[a, b, c]
  45. 字符串为：a
  46. 第2次循环，操作前的集合为[b, c]
  47. 字符串为：ab
  48. 第3次循环，操作前的集合为[c]
  49. 字符串为：abc
  50. for循环结束后，字符串为abc  集合为：[]
复制代码
作者: polarfox17    时间: 2015-9-25 00:39
你这个方法是用来干什么的呀，怎么两个void，
第一，可能你说的index为0的时候，remove方法移除的是index这个角标位的元素，其他的位置还是有元素的，所以不会出现空集合，
第二，递归的方法都必须设定一个条件，当他满足的时候停止递归，开始返回值，楼主你的递归好像停不下来
我也是新手，有什么不对的地方请轻喷
作者: Jusive    时间: 2015-9-25 06:38
递归最怕的就是循环部队成了死递归，请检查一下循环，建议不要使用递归去做循环
作者: thriver2010    时间: 2015-9-25 14:11
来看大神
作者: fcl13761179064    时间: 2015-9-25 19:01
递归的意思是alcopy给str一个元素，然后alcopy移除已经传递的元素，按照道理当al.size()=0时应该停止递归。remove移除元素后，位置会空下来吗？如果会完全没必要也不应该使用递归；
作者: 清心玉质    时间: 2015-9-26 10:52
经高人指点，我理解是这样 当复制集合空了以后 ，即index=0，停止递归 但循环进展到index=1，al集合还是原集合再重新开始递归，直到运行完index=al。size-1后，循环和递归才停止。
作者: 清心玉质    时间: 2015-9-26 10:54
实际上看起来也是这样，但是我还没搞懂得是，为什么复制集合空了，没把空集合传回去，循环和递归都结束，而是又重新开始了原al的index=1次循环递归。希望有人指点



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2