递归算法

    递归（recursion）是一种描述和解决问题的基本方法，用来解决可归纳描述的问题，或者说可分解为结构自相似的问题。所谓结构自相似，是指构成问题的部分与问题本身在结构上相似。这类问题具有的特点是：整个问题的解决可以分为两个部分，第一部分是一些特殊或基本情况，可直接解决；第二部分与原问题相似，可以类似的方法解决，但比原始问题的规模小。

 

这类问题在数学中很常见，例如求    n！

算法如下：

long fact(int n)

{    if(n==1)

     return 1;    //第一部分

          else  

          return n*fact(n-1);    //第二部分，递归

}

在该式中，f（n-1）的计算与原问题f（n）的计算相似，只是规模更小。

 

 

再看一个例子，题目：设一维数组A的元素A[k1]--A[k2]中存放在整数，用递归方法求出他们中的最大者，并作为函数值返回。

显然，若k1 = k2，即数组中只有一个元素，则A[k1]就是最大元素；若k1 < k2,则用类似的方法先求出A[k1+1]--A

[k2]中的最大者m，然后令m与A[k1]进行比较，二者中的最大者即为所求。

 

算法如下：

int maxint(int A[],int k1,int k2)          //求A[k1]--A[k2]中的最大者,并返回

{      if(k1 == k2) 

         return  A[k1];

          else {

                     m = maxint(A,k1+1,k2);

                     return(A[k1] > m)?A[k1]:m;

                   }

}