递归的应用，输出字符串的所有排列（java）


看到一个题目：输出一个字符串的所有排列。

大致想了一下，觉得需要用到递归，而递归是我不太擅长的，所以就想练一下。

在知道递归之前，容易想到的一种办法是：

假设字符串为s，那么写一个有s.length()层嵌套的循环~~~在循环的最内层输出结果~~~

形如：

 
      
              for(int i = 0;i)
          for(int j = 0;j)
              for(int k = 0;k)
                  for(int l = 0;l)
                      for(int m = 0;m)
                           System.out.println(""+s.charAt(i)
                                   +s.charAt(j)
                                  +s.charAt(k)
                                  +s.charAt(l)
                                  +s.charAt(m));
                       }
                   }
               }
           }
       } 

      

      



这个方法比较容易实现，算法也简单，但是有一个前提——字符串s的长度必须是已知的，否则就会不知道要写几层循环~~尴尬

而且如果字符串很长，比如100，就要写可怕100层循环~~(当然，真是100的话估计计算机会表示压力很大，内存不足~~)

——显然这不是一个很好的办法。

对递归有些了解之后，就会想到，这题用递归会很合适。

费了很大的劲，写出了如下代码——

   public class Main {

    static int c = 0;

    public static void main(String[] args) {
        String s = "1234";
        printAllArray(s);
    }

    private static void printAllArray(String s) {
        printAllArray(s, "");
    }

    private static void printAllArray(String s, String n) {
        if (s.length() == 0) {
            System.out.println(n + "  ---  " + ++c);
        } else {
            for (int i = 0; i < s.length(); ++i) {
                printAllArray(s.substring(1), n + s.charAt(0));
                s = s.substring(1) + s.charAt(0);
            }
        }
    }

 结果：

1234  ---  1
1243  ---  2
1342  ---  3
1324  ---  4
1423  ---  5
1432  ---  6
2341  ---  7
2314  ---  8
2413  ---  9
2431  ---  10
2134  ---  11
2143  ---  12
3412  ---  13
3421  ---  14
3124  ---  15
3142  ---  16
3241  ---  17
3214  ---  18
4123  ---  19
4132  ---  20
4231  ---  21
4213  ---  22
4312  ---  23
4321  ---  24

14行以后是递归的应用，也是这段代码的核心

递归：就是自己调用自己。

递归是需要结束条件的，要不然就是无尽的循环了，在这段代码中，结束条件在15行， if (s.length() == 0) 即当传递的参数s长度为0时结束递归。

函数接收的参数为字符串s和n，每次在函数内部调用自身，即一个递归调用，参数为s.substring(1)和 n + s.charAt(0));   每次调用的参数都会是参数s的长度减少1，

而n增加1，直到结束条件s.length() == 0为真，递归结束，打印一个结果。

递归会进行s.length()次，而且函数调用自身的地方位于循环 for (int i = 0; i < s.length(); ++i) 中，所以会打印出s.length()!次结果。这与数学分析的结果是一致的。

20行  s = s.substring(1) + s.charAt(0); 是必须的，它的作用是使字符串平移一位，如s为"1234"，执行此句后就变为了"2341"，保证每次产生不重复的结果。

个人认为：

递归的优点在于：一些问题用递归编程时能使思路非常清晰、代码简洁。

而缺点同样很明显：占用内存将很大。

一个例子，求n阶乘的两种方法

       /**
     * 使用递归求n的阶乘
     */
    int fun1(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n * fun1(n - 1);
        }
    }

    /**
     * 使用循环求n的阶乘
     */
    int fun2(int n) {
        int x = 1;
        for (int i = 1; i <= n; ++i) {
            x *= i;
        }
        return x;
    }
}

 体会之。

 受东平小同学蛊惑，第一次用writer写文章，感觉还好。

递归的应用，输出字符串的所有排列（java）

浏览过的版块