数据结构4——递归算法

递归算法：开始不断的调用自己，直到到达递归的出口，当到达递归的出口之后，最后调用的最先返回。做递归算法最重要的是找到出口。

就好比栈，开始一直往栈里面装入东西，直到抵达出口的时候才开始往外面拿东西。

图示左边先不断的调用，右边是从栈顶开始不断的返回。

实例1：求阶乘

 1 package com.hone.recursion;
 2 
 3 public class fact {
 4     public static long fact(int n){
 5         int x;
 6         long y;
 7         
 8         if (n<0) {
 9             System.out.println("请输入正确的参数");
10         }
11         if (n==0) return 1;
12         else{
13             x=n-1;
14             y=fact(x);
15             return n*y;
16         }
17     }
18     
19     public static void main(String[]  args){
20         long fn;
21         fn=fact(3);
22         System.out.println("fn= "+fn);
23         
24     }
25 }

过程图

实例2：用对半法来查找

 1 package com.hone.recursion;
 2 
 3 public class BinSearch {
 4     public static int bSearch(int[] a, int x, int low,int high){
 5         int mid;
 6         if (low>high) return -1;
 7         
 8         mid=(low+high)/2;
 9         if (a[mid]>x) {
10             return bSearch(a, x, low, mid-1);
11         }
12         else if (a[mid]<x) {
13             return bSearch(a, x, mid+1, high);
14         }
15         else 
16             return mid;
17     }
18     
19     public static void main(String[] args) {
20         int[] a={1,4,6,9,11,14,17,23,33,36,79,119,345,678,890};
21         int x=33;
22         int low=0;
23         int high=a.length-1;
24         System.out.println(high);
25         int re=bSearch(a, x, low, high);
26         if(re==-1){
27             System.out.println("x不在数组中....");
28         }
29         else{
30             System.out.println("x在数组中的下标值为："+re);
31         }
32     }
33 }

实例3：汉诺塔游戏

 1 package com.hone.recursion;
 2 
 3 public class HanNoiTower {
 4     
 5     public static void towers(int n ,char from ,char To, char aux){
 6         
 7         if (n==1) {
 8             System.out.println("Move disk 1 from "+from +" To "+To);
 9             return ;
10         }
11         
12         //思路，首先应该将n-1个盘子在C的帮助下从A移到B
13         towers(n-1, from, aux, To);
14         
15         //在将盘子n从A直接移动c中 
16         System.out.println("move disk "+n +" from " +from+" To "+ To);
17         
18         //再将剩余的n-1个盘子在A的帮助下从B移动到C中
19         towers(n-1, aux, To, from);
20     }
21     public static void main(String[] args) {
22         towers(4, 'A', 'B', 'C');
23     }
24 
25 }

汉诺塔用递归调用是最好的实例，你只需要有大致的思路，其他的都可以交给算法来处理。

了解递归的运行过程，最好的办法就是用debug模式来分析程序运行的过程。

在很多情况下，递归能实现的事情，通常循环也可以实现。而且循环所需要的时间复杂度远远的低于递归的时间复杂度。