简单的说，递归就是函数自己调用自己。在数据结构里面会经常使用递归，因为递归代码比较简洁优雅，易懂。

编写递归程序时主要注意三点

（1）递归总有一个最简单的情况，方法的第一条语句总是包含return的条件语句

（2）递归调用总是去尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况。在下面代码中，第四个参数和第三个参数的差值一直在缩小

（3）递归调用的父问题和尝试解决的子问题之间不应该有交集。在如下代码中，两个子问题，各自操作的数组部分是不同的

下面是二分法查找的递归实现和非递归实现；

特别注意一点，二分查找技术，是针对有序的数组和顺序表，不能忘记前提

//使用递归实现二分法查找,同时使用函数重载    public static int rank(int key,int a[])    {        return rank( key,a,0,a.length-1);    }    public static int rank(int key,int[]a,int lo,int hi)    {        if(lo>hi)            return -1;        int mid=lo+(hi-lo)/2;        if(key
     
      a[mid])            return rank(key,a,mid+1,hi);        else            return mid;    }
     

二分查找算法的非递归实现

public static int BinarySearch(int arr[],int key){    int low,high,mid;    low=0;    high=arr.length-1;    while(low<=high)    {        mid=low+(high-low)/2;        if(key
     
      arr[mid])            low=mid+1;        else            return mid;    }    return 0;}