一、递归算法设计的基本思想是: 对于一个复杂的问题,把原问题分解为若干个相对简单类同的子问题,继续下去直到子问题简单到能够直接求解,也就是说到了递推的出口,这样原问题就有递推得解。 在做递归算法的时候,一定要把握住出口,也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口是非常好理解的,就是一个条件,当满足了这个条件的时候我们就不再递归了。
关键要抓住的是:
(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>
总结递归算法来说,这个根就是那个出口,只要找到这个出口所在,那么算法自然而然就能水到渠成了。 |