递归函数

函数可以调用其他函数，也可以调用自身
递归函数(Recursive Function),即自调用函数,在函数体内有直接的或间接地自己调用自己的语句
递归函数很特殊，因为自己调用自己，很容易出现死循环
因此自调用过程在函数内必须设置某些条件，当条件成立时终止自调用过程，并使程序控制逐步从函数中返回,称为条件递归\

递归程序必然包含两部分：

递归循环继续的过程
递归调用结束的过程

递归程序分析：

根据观察，找到输入变量：m1,m2…mn
设求的递归函数是f(m1,m2…mn)
前一个项和后一个项肯定是有关系的，不然递归无法进行。即f(m1n,m2n…mnn)与f(m1n-1,m2n-1…mnn-1)之间有一定关系

例1:求n的阶乘
    算法分析：
    n=0 n!=1; 
    n!=0 n!=n*(n-1)!

int Factorial(int n)
{
    if(n==0)return 1;                    递归结束条件       
    if(n!=0)return Factorial(n-1)*n;     
}

函数调用过程：
函数递归调用自身时，每次调用都会得到一个与以前的自动变量集合不同的新自动变量集合
以n=3为例，首先n!=0,Factorial(3)=Factorial(2)*3，此处Factorial(3)调用了Factorial(2)
进入Factorial(2)，n=2,n!=0, Factorial(2)=Factorial(1)*2,同理，继续调用Factorial(1)
进行3次递归后，n==0,此时返回Factorial(0)=1
将Factorial(0)依次向上传递后，得到Factorial(3)的结果
Factorial()属于尾递归，即递归调用位于函数体的结尾处，除了尾递归外还有中间递归，多层递归等\

例2:一个能够较好说明递归的例子是快速排序，快速排序算法是C.A.R.Hoare于1962年发明的
    对于一个给定数组，从中选择一个元素，以该元素为界将其余元素划分为两个子集
    一个子集中所有元素都小于该元素，另一个子集中所有元素都大于或等于该元素
    对这样两个子集递归执行这一过程，当某个子集元素数小于2时，这个子集就不需要排序，终止递归
    每次划分子集时，选取各个子数组的中间元素，从执行速度上来讲此算法版本的快速排序可能不是最快，但是最简单的算法之一
void swap(int t[],int a,int b)                                         因为单次递归过程要交换三次元素
{                                                                      所以将其单独封装为函数
    int tmp;
    tmp=t[a],t[a]=t[b],t[b]=tmp;
}
void qsort(int t[],int start,int end){                                 KR书上的快速排序
    int pivot,i;
    if(end<=start)return;                                              若数组元素数小于2，不进行任何操作
    swap(t,start,(start+end)/2);                                       划分子集的元素(枢轴)移动到v[0]
    pivot=start;
    for(i=start+1;i<=end;i++)if(t[i]<t[start])swap(t,++pivot,i);       划分子集
    swap(t,start,pivot);                                               恢复枢轴元素
    qsort(t,start,pivot-1);
    qsort(t,pivot+1,end);
}
标准库中提供了一个qsort函数，可用于对任何类型的对象排序

函数调用之间用参数传递和返回值联系
递归调用机制是由栈数据结构实现的
使用递归函数使程序代码和递归关系几乎一致，代码紧凑，可读性很强，直观精炼，符合人的思维习惯，接近数学公式的表示，更易于编写和理解，
递归尤其适合非数值计算领域，如：汉诺塔，骑士游历，八皇后问题
在描述树等递归定义的数据结构时使用递归尤其方便
但递归不断调用函数并在栈中分配空间保存参数返回地址，会大量增加系统开销，时间空间消耗都较高，执行效率低下
因此在很多需要运行效率的场合中需要将递归转为非递归形式\

递归函数示例程序：找出a和b的最大公约数
    算法分析：
    a和b的最大公约数是b和a%b的最大公约数
    a=kb+a%b=kb+r,r<nb,n>=2
    充分性证明：
    设d为(a,b)的最大公约数，则d可以整除b和kb+r，所以d整除r，所以d是(b,a%b)的公约数
    如果(b,a%b)存在比d大的公约数d'，则d'可以整除kb+r，d不是(a,b)的最大公约数，矛盾
    因此d是(b,a%b)的最大公约数
    必要性证明：
    设d为(b,r)的最大公约数，则d可以整除b和r，因此可以整除a=kb+r，因此d是a和b的公约数
    同理，如果(a,b)存在比d大的公约数d''，则d''可以整除r，dd是(a,b)的最大公约数
#include<stdio.h>
int Divisor(int a,int b)
{
    if(a>=b)
    {
        if(a%b==0)return b;
        else return Divisor(b,a%b);
    }
}
int main()
{
    printf("%d",Divisor(43278,4237));     输出结果：1
}
Divisor()也可以转换为非递归形式(迭代)         递归中一定有迭代，但是迭代中不一定有递归；大部分可以相互转换。
int Divisor(int a,int b)            
{
    int tmp;
    while(a%b!=0)
    {
        tmp=a;
        a=b;
        b=tmp%a;
    }
    return b;
}