递归.txt

数据结构是计算机学科的一门核心课程。数据结构课程的 任务是讨论现实世界中数据的各种逻辑结构、在计算机中的存 储结构以及实现各种操作的算法等问题。掌握如何组织数据、 如何存储数据和如何处理数据的基

递归   

 定义：若一个算法直接地或间接地调用自己本身，则称这个算
法是递归算法，简称递归。
    递归算法用把问题分解为形式更加简单的子问题的方法来求解
问题。递归算法既是一种分析问题的方法，也是一种有效的算法设
计方法。递归算法是解决许多复杂应用问题的重要方法。
                          

                          递归算法的执行过程

例1：给出按照公式计算阶乘函数的递归算法，并给出n=3时递归算
法的执行过程。
设计：按照公式  /当n=0时 n!=0        
                \当n>0时 n!=n*(n-1) 
计算阶乘函数的递归算法如下：
               
long int Fact(int n)
{
     int x;
     long int y;
     
     if(n<0)                     /*n<0时阶乘无定义*/
     {
         printf("参数错!");
         return -1; 
     }
     
     if(n==0) return 1;
     else
     {
         y=Fact(n-1);            /*递归调用*/
         return n*y;
     }
}


例2：给出在有序数组a中查找数据元素x是否存在的递归算法。
设计： 算法的参数为：有序数组a，要查找的数据元素x，数组下界
下标low，数组上界下标high。当在数组a中查找到数据元素x时函数
返回数组a的下标；当在数组a中查找不到数据元素x时函数返回一1。
  递归算法如下:
  
int BSearch(int a[],int x,int low,int high)
{
     int mid;

     if(low>high) return -1;              /*查找不成功*/

     mid=(low+high)/2;

     if(x==a[mid]) return mid;            /*查找成功*/
     else if(x<a[mid])
         return BSearch(a,x,low,mid-1);   /*在下半区查找*/
     else
         return BSearch(a,x,mid+1,high);  /*在上半区查找*/
}