A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© bestcaptain 中级黑马   /  2016-2-25 22:32  /  583 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文


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

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

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

关键要抓住的是:
(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>  




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

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马