递归算法

用三角数字问题说明递归

Int triangle(int n)

{

       if(n ==1)        //基值条件

              return 1;

       else

              return(n + triangle(n-1));              //递归调用自身

}

说明：导致递归的方法返回而没有再一次进行递归调用，这称为基值情况。

从上面可以看出递归方法的特征：

1， 调用自身

2， 当它调用自身的时候，它这样做是为了解决更小的问题。

3， 存在某个足够简单的问题的层次，在这一层算法不需要调用自己就可以直接解答，且返回结果。

递归的效率问题：调用一个方法总要有一定的额外开销。控制必须从这个调用的位置转 移到这个方法的开始处。而且，传给这个方法的参数以及这个方法的返回的地址都要被压入一个内部的栈里。正因此，递归降低了执行效率。另外，中间参数以及返 回值要占内存，如果数据量大的话，可能会造成栈溢出。

递归的好处就在于它从概念上简化了问题。

计算阶乘也是一个递归的经典例子，另外找两个数的最大公约数、求一个数的乘方等很多数学问题都可以用递归的思想来解决。

用递归方法解决变位字问题

假设要列出一个指定单词的所有变位字，也就是列出该词的全排列，它们都是由原来单词的字母组成。我们称这个工作是变位一个单词或称全排列一个单词。

解决思想：假设这个词有n个字母。

1， 全排列最右边的n-1个字母。

2， 轮换所有n个字母。

3， 重复以上步骤n次。

“轮换”这个词意味着所有的字母向左移一位，最左边的字母轮换至最右边字母的后 边。轮换单词n次以给每个字母排在开头的机会。当选定字母占据第一个位置时，所有其他字母被全排列。如何来全排列最右边的n-1个字母呢？通过递归，即调 用方法自身。每调用一次自身，全排列的字母数减少1，当词的大小只剩一个字母时即出现基值条件，方法返回。

       public static void doAnagram(int newSize)

       {

              if(newSize == 1)    //if too small,go no further

                     return;

              for (int j=0; j<newSize; j++) //for each position

              {

                     doAnagram(newSize - 1);      //anagram remaining

                     if (newSize == 2)   //if innermost,

                     {

                            displayWord();       //display it

                     }

                     rotate(newSize);     //rotate word

              }

       }

递归的二分查找

用最少的比较次数在一个有序的数组中找到给定的一个数据项。二分查找的方法是把数组从中间分为两半，然后看要查找的数据项在数组的哪一半，再次地折半，如此进行下去。下面是此方法的递归实现代码：

       private int recFind(long searchKey,int lowerBound,int upperBound)

       {

              int curIn;

              curIn = (lowerBound + upperBound) / 2;

              if(a[curIn]==searchKey)

                     return curIn;          //find it

              else                              //can't find it

              {

                     if (a[curIn] < searchKey)      //it's in upper half

                            return recFind(searchKey,curIn+1,upperBound);

                     else                                     //it's in lower half

                            return recFind(searchKey,lowerBound,curIn-1);

              }     //end else divide range

       }            //end recFind

二分查找是分治算法的一个例子。把一个大问题分成两个相对来说更小的问题，并且分别解决每一个小问题。对于每个小问题的解决方法也是一样的，每个小问题又分成两个更小的问题。一直持续下去直到达到易于求解的基值情况，就不用再分了。

分治算法通常是一个方法，在这个方法中含有两个对自身的递归调用，分别对应于问题的两个部分。在二分查找中，有两个这样的调用，不过只有一个真的执行。后面的归并排序是真正执行了两个递归调用。

归并排序

归并算法的中心是归并两个已经有序的数组。归并两个有序的数组A和B，就生成了第三个数组C，数组C包含数组A和B的所有数据项，并且使它们有序的排列在数组C中。做法就是用三个while循环，第一个循环沿A和B走，比较它们的数据项，并且复制它们中较小的数据项到数组C。后面两个循环分别对应B的数据项已经全部移出，而C中还有剩余元素的情况，和B中还有剩余，C已经全部移出的情况。循环就是把数组中剩余的数据项复制到C中。

归并排序的思想是把一个数组分成两半，排序每一半，然后用归并方法把数组的两半归并成一个有序的数组。而为每一半进行排序，就用递归。即把每个一半都分成两个四分之一，对每个四分之一部分排序，然后把它们归并成一个有序的一半。

归并排序的基值条件，就是当发现mergeSort（）方法发现只有一个数据项的数组时，它就返回。把这两个数据项归并到一个有两个数据项的数组中。还要建一个工作空间数组，，它和初始数组一样大小。归并得到的数组存储到工作空间数组中，每一次归并完成之后，工作数组的内容被复制回原来的数组中。

归并排序的运行时间是O(N*logN)

下面是归并排序的完整代码：

 

class MergeSortApp
{
    private static long[] theArray;
    private static int nElems;

    public static void display()
    {
        for(int j=0;j<nElems;j++)
            System.out.print(theArray[j] + " ");
        System.out.println("");
    }

    public static void mergeSort()
    {
        long[] workSpace = new long[nElems];    //provides workspace
        recMergeSort(workSpace,0,nElems-1);
    }

    private static void recMergeSort(long[] workSpace,int lowerBound,int upperBound)
    {
        if(lowerBound == upperBound)    //if range is 1,no use sorting
            return;
        else
        {                                
            int mid = (lowerBound+upperBound)/2;    //find midpoint

            recMergeSort(workSpace,lowerBound,mid);    //sort low half

            recMergeSort(workSpace,mid+1,upperBound);    //sort high half

            merge(workSpace,lowerBound,mid+1,upperBound);    //merge them
        }
    }

    private static void merge(long[] workSpace,int lowPtr,int highPtr,int upperBound)
    {
        int j=0;        //workspace index
        int lowerBound = lowPtr;    //因为随着归并的进行，lowPtr会变化，lowerBound变量用于记住该变量，
                                    //以备将归并后的数据拷贝回原数组时使用
        int mid = highPtr-1;
        int n = upperBound-lowerBound+1;        //# of items

        while (lowPtr <= mid && highPtr <= upperBound)
        {
            if(theArray[lowPtr] < theArray[highPtr])
                workSpace[j++] = theArray[lowPtr++];
            else
                workSpace[j++] = theArray[highPtr++];
        }

        while (lowPtr <= mid)
        {
            workSpace[j++] = theArray[lowPtr++];            
        }

        while (highPtr <= upperBound)
        {
            workSpace[j++] = theArray[highPtr++];
        }

        for (j=0; j<n; j++)
        {
            theArray[lowerBound+j] = workSpace[j];
        }
    }
    
    public static void main(String[] args) 
    {
        theArray = new long[]{64,21,33,70,12,85,44,3,99,0,108,36};
        nElems=12;

        display();    //display items

        mergeSort();    //merge sort the array

        display();    //display again
    }
}

 

消除递归：递归和栈有紧密的联系，大部分编译器都是使用栈来实现递归的。可以用栈实现把递归算法转换成非递归的算法。

递归应用

求一个数的乘方：基于x的y次方等于x*x的y/2次方这个原理

背包问题：从选择第一个数据项开始，剩余的数据项的加和必须符合背包的目标重量减去第一个数据项的重量；这是一个新的目标重量。逐个试每种数据项组合的可能性，如果没有组合合适的话，放弃第一个数据项，并且从第二个数据项开始再重复整个过程。依次进行下去。

组合问题：从n个人中选出k个组队，有多少种组合？（n,k）= (n-1, k-1) + (n, k-1)