黑马程序员技术交流社区

标题: java递归算法实例小结 [打印本页]

---

作者: bestcaptain    时间: 2016-2-25 22:32
标题: java递归算法实例小结

一、递归算法设计的基本思想是：

        对于一个复杂的问题，把原问题分解为若干个相对简单类同的子问题，继续下去直到子问题简单到能够直接求解，也就是说到了递推的出口，这样原问题就有递推得解。

      在做递归算法的时候，一定要把握住出口，也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口是非常好理解的，就是一个条件，当满足了这个条件的时候我们就不再递归了。

关键要抓住的是：
（1）递归出口

（2）地推逐步向出口逼近

二、递归算法实例

（1）阶乘：

          要求：给定一个数值，计算出它的阶乘值，例如5的阶乘为5*4*3*2*1

          实现：

• <span style="font-size:12px;">  // 利用递归实现一个数的阶乘值  
•     private static BigDecimal getNum(BigDecimal inNum) {  
•         if (inNum.compareTo(BigDecimal.ONE) == 0) {  
•             return inNum;  
•         }  
•         return inNum.multiply(getNum(inNum.subtract(BigDecimal.ONE)));  
•     }</span>  
  

（2）Fibonacci数列：1，1，2，3，5，8，13……

           要求：找出数列中指定index位置的数值

           实现：

• <span style="font-size:12px;">  // 利用递归实现了Fibonacci数列  
•     private static int fab(int index) {  
•         if (index == 1 || index == 2) {  
•             return 1;  
•         } else {  
•             return fab(index - 1) + fab(index - 2);  
•         }  
•     }</span>  
  

（3）汉诺塔

          要求：汉诺塔挪动

          实现：

• <span style="font-size:12px;">  <span style="white-space:pre">  </span>private static final String DISK_B = "diskB";  
•   <span style="white-space:pre">    </span>private static final String DISK_C = "diskC";  
•   <span style="white-space:pre">    </span>private static final String DISK_A = "diskA";  
•   <span style="white-space:pre">    </span>static String from=DISK_A;  
• <span style="white-space:pre">  </span>  static String to=DISK_C;  
• <span style="white-space:pre">  </span>  static String mid=DISK_B;  
•   
• <span style="white-space:pre">  </span>  public static void main(String[] args) {  
• <span style="white-space:pre">  </span>      String input=JOptionPane.showInputDialog("please input the number of the disks you want me move.");  
• <span style="white-space:pre">  </span>      int num=Integer.parseInt(input);  
• <span style="white-space:pre">  </span>      move(num,from,mid,to);  
• <span style="white-space:pre">  </span>  }</span>  
  

• <span style="font-size:12px;">  // 利用递归实现汉诺塔  
•     private static void move(int num, String from2, String mid2, String to2) {  
•         if (num == 1) {  
•             System.out.println("move disk 1 from " + from2 + " to " + to2);  
•         } else {  
•             move(num - 1, from2, to2, mid2);  
•             System.out.println("move disk " + num + " from " + from2 + " to " + to2);  
•             move(num - 1, mid2, from2, to2);  
•         }  
•     }</span>  
  

（4）排列组合

          要求：将输入的一个字符串中的所有元素进行排序并输出，例如：你给出的参数是"abc"，

                      则程序会输出

                      abc
                      acb
                      bac
                      bca
                      cab
                      cba

          实现：

• <span style="font-size:12px;"><span style="white-space:pre">    </span>public static void permute(String str) {  
• <span style="white-space:pre"> </span>   char[] strArray = str.toCharArray();  
•   <span style="white-space:pre">    </span> permute(strArray, 0, strArray.length - 1);  
• <span style="white-space:pre">  </span>}</span>  
• 
  
  

• <span style="font-size:12px;">  // 利用递归实现，将输入的一个字符串中的所有元素进行排序并输出  
•     public static void permute(char[] list, int low, int high) {  
•         int i;  
•         if (low == high) {  
•             String cout = "";  
•             for (i = 0; i <= high; i++) {  
•                 cout += list;  
•             }  
•             System.out.println(cout);  
•         } else {  
•             for (i = low; i <= high; i++) {  
•                 char temp = list[low];  
•                 list[low] = list;  
•                 list = temp;  
•                 permute(list, low + 1, high);  
•                 temp = list[low];  
•                 list[low] = list;  
•                 list = temp;  
•             }  
•         }  
•     }</span>  
  
  

总结递归算法来说，这个根就是那个出口，只要找到这个出口所在，那么算法自然而然就能水到渠成了。

---

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

黑马程序员IT技术论坛 X3.2