java递归算法实例小结

默然苏 贡献于2017-01-17

作者 苏燕晖  创建于2016-03-07 06:18:00   修改者苏燕晖  修改于2016-03-07 06:19:00字数2869

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

JAVA递归算法实例小结 标签: 算法java 2012-07-05 11:23 25949人阅读 评论(0) 收藏 举报  分类:   JAVA(5)  一、递归算法设计的基本思想是:         对于一个复杂的问题,把原问题分解为若干个相对简单类同的子问题,继续下去直到子问题简单到能够直接求解,也就是说到了递推的出口,这样原问题就有递推得解。       在做递归算法的时候,一定要把握住出口,也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口是非常好理解的,就是一个条件,当满足了这个条件的时候我们就不再递归了。 关键要抓住的是: (1)递归出口 (2)地推逐步向出口逼近 二、递归算法实例 (1)阶乘:           要求:给定一个数值,计算出它的阶乘值,例如5的阶乘为5*4*3*2*1           实现: [html] view plain copy  print? 1.   // 利用递归实现一个数的阶乘值   2.     private static BigDecimal getNum(BigDecimal inNum) {   3.         if (inNum.compareTo(BigDecimal.ONE) == 0) {   4.             return inNum;   5.         }   6.         return inNum.multiply(getNum(inNum.subtract(BigDecimal.ONE)));   7.     }   (2)Fibonacci数列:1,1,2,3,5,8,13……            要求:找出数列中指定index位置的数值            实现: [html] view plain copy  print? 1.   // 利用递归实现了Fibonacci数列   2.     private static int fab(int index) {   3.         if (index == 1 || index == 2) {   4.             return 1;   5.         } else {   6.             return fab(index - 1) + fab(index - 2);   7.         }   8.     }   (3)汉诺塔           要求:汉诺塔挪动           实现: [html] view plain copy  print? 1.     private static final String DISK_B = "diskB";   2.       private static final String DISK_C = "diskC";   3.       private static final String DISK_A = "diskA";   4.       static String from=DISK_A;   5.     static String to=DISK_C;   6.     static String mid=DISK_B;   7.    8.     public static void main(String[] args) {   9.         String input=JOptionPane.showInputDialog("please input the number of the disks you want me move.");   10.         int num=Integer.parseInt(input);   11.         move(num,from,mid,to);   12.     }   [html] view plain copy  print? 1.   // 利用递归实现汉诺塔   2.     private static void move(int num, String from2, String mid2, String to2) {   3.         if (num == 1) {   4.             System.out.println("move disk 1 from " + from2 + " to " + to2);   5.         } else {   6.             move(num - 1, from2, to2, mid2);   7.             System.out.println("move disk " + num + " from " + from2 + " to " + to2);   8.             move(num - 1, mid2, from2, to2);   9.         }   10.     }   (4)排列组合           要求:将输入的一个字符串中的所有元素进行排序并输出,例如:你给出的参数是"abc",                       则程序会输出                       abc                       acb                       bac                       bca                       cab                       cba           实现: [html] view plain copy  print? 1.     public static void permute(String str) {   2.      char[] strArray = str.toCharArray();   3.        permute(strArray, 0, strArray.length - 1);   4.   }   [html] view plain copy  print? 1.   // 利用递归实现,将输入的一个字符串中的所有元素进行排序并输出   2.     public static void permute(char[] list, int low, int high) {   3.         int i;   4.         if (low == high) {   5.             String cout = "";   6.             for (i = 0; i <= high; i++) {   7.                 cout += list[i];   8.             }   9.             System.out.println(cout);   10.         } else {   11.             for (i = low; i <= high; i++) {   12.                 char temp = list[low];   13.                 list[low] = list[i];   14.                 list[i] = temp;   15.                 permute(list, low + 1, high);   16.                 temp = list[low];   17.                 list[low] = list[i];   18.                 list[i] = temp;   19.             }   20.         }   21.     }  

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档