函数递归

递归

• 定义：直接或间接在函数体内调用函数本身，实现循环。

直接：在函数体本身调用自己函数本身。
间接：例如：存在2个函数fun1（）和fun2（）那么，在fun1（）函数中调用fun2（）函数，在fun2（）函数中调用fun1（）函数。

• 注意事项：任何一个函数体内不能出现其他函数的定义。

n！的递归算法

#include <stdio.h>
int jc(int n); 
int main()
{
    int n;
    scanf ("%d",&n);
    printf ("%d\n",jc(n));  
}
int jc(int n)
{
    int f=1;
    if(n==0)
        return 1;
    else
        f=n*jc(n-1);    
    return f;
}

以n==4为例

函数递归，最难理解的就是如何返回，这张图片很好的介绍了函数的返回。

冒泡排序的递归算法

• 思路：将最大数放置最后，再讲次大数放置在倒数第2位，以此类推
• 代码实现

for(int i=0;i<n;i++)
  for(int j=0;j<n-i;j++)
    if(a[j]<a[j+1]
      swap(a[j],a[j+i])

• 由此可知，递归的出口就是i>=n，i,j的变换条件是j>=n-i。

void mppx(int n,int i,int j,int a)
{
    if(i>=n)
         return ;
    else if(j>=n-i)
         i++,j=0;
    if(a[j]<a[j+1])
         swap(a[j],a[j+1])
    mppx(n,i,j,a);
}

这个swap()函数，可以使用库函数，也可以自己定义函数。

swap(int *p1,int *p2)
{
  int a;
  a=*p1;
  *p1=*p2;
  a2=a;
}
main()
{
  int m,n;
  scanf ("%d%d",&m,&n);
      if(m>n)
         swap(&m,&n);
  printf ("%d,%d",m,n); 
}

函数的难点就是函数递归，对于循环问题都可以用递归来写。

递归与循环

• 递归函数会重复调用自身函数。
• 无限循环将继续重复执行相同的代码。

虽然听起来两者非常相似，但实际效果却截然不同。

• 递归：在无数次调用的时候，变量会被压入堆栈区，即函数递归的次数存在限制，也就是说，实际中运行无限递归时，耗尽堆栈空间，程序停止，当然它很有可能会使堆栈溢出，然后*结束。
• 循环：while循环会一直使用相同的空间，因此循环可以永远运行，最起码到电源熄灭之前。