C语言 – 递归函数

一个函数在它的函数体内调用它自身称为递归调用，这种函数称为递归函数。执行递归函数将反复调用其自身，在递归调用中，主调函数又是被调函数。执行递归函数将反复调用其自身，每调用一次就进入新的一层。

例如有函数 recurse 如下：

这个函数是一个递归函数。但是运行该函数将无休止地调用其自身，这当然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。

常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。

下面举例说明递归调用的执行过程。

执行递归函数将反复调用其自身，每调用一次就进入新的一层，当最内层的函数执行完毕后，再一层一层地由里到外退出。

考虑一个数字的阶乘，其计算公式如下6！ = 6 * 5 * 4 * 3 * 2 * 1。重复计算fact*（fact-1）直到fact等于1。

例1.利用递归函数计算6的阶乘

#include <stdio.h>
int factorial(int number);
 
int main() 
{    
  int x = 6;
  printf("The factorial of %d is %d\n", x, factorial(x)); 
  return 0;
}
 
int factorial(int number) 
{
  if (number == 1)   
     return (1); /* exiting condition */
  else
    return (number * factorial(number - 1));
} 

factorial() 就是一个典型的递归函数。调用 factorial() 后即进入函数体，只有当 n==1 时函数才会执行结束，否则就一直调用它自身。

由于每次调用的实参为 n-1，即把 n-1 的值赋给形参 n，所以每次递归实参的值都减 1，直到最后 n-1 的值为 1 时再作递归调用，形参 n 的值也为1，递归就终止了，会逐层退出。

 

A. 声明一个函数，该函数接受一个整数参数并返回该参数的阶乘。此函数将调用自身并减少参数值直到退出或达到基本条件为止。当条件为真时，先前生成的值将彼此相乘，并返回最终的阶乘值。

B. 声明并初始化一个值为“ 6”的整数变量，然后通过调用阶乘函数来打印其阶乘值

考虑下图，以更深入地了解递归机制，该机制包括调用函数自身直至达到基本情况或停止条件，然后再收集先前的值：

 

例2.利用递归函数计算自然数之和

 include <stdio.h>
int sum(int n);

int main() {
    int number, result;

    printf("Enter a positive integer: ");
    scanf("%d", &number);

    result = sum(number);

    printf("sum = %d", result);
    return 0;
}

int sum(int n) {
    if (n != 0)
        // sum() function calls itself
        return n + sum(n-1); 
    else
        return n;
}

结果

最初，从 main() 函数调用 sum()，并将数字作为参数传递。

假设 sum() 中 n 的值最初是 3。在下一次函数调用期间，将 2 传递给 sum() 函数。这个过程一直持续到 n 等于 0。

当 n 等于 0 时，if 条件失败并执行 else 部分，最终将整数总和返回给 main() 函数。

例3.用递归法计算 n! 

long ff(int n)
{
   long f;
   if(n<0) printf("n<0,input error");
   else if(n==0||n==1) f=1;
   else f=ff(n-1)*n;
   return(f);
}
main()
{
   int n;
   long y;
   printf("\ninput a inteager number:\n");
   scanf("%d",&n);
   y=ff(n);
   printf("%d!=%ld",n,y);
}

 

 

递归的条件

每一个递归函数都应该只进行有限次的递归调用，否则它就会进入死胡同，永远也不能退出了，这样的程序是没有意义的。

要想让递归函数逐层进入再逐层退出，需要解决两个方面的问题：

• 存在限制条件，当符合这个条件时递归便不再继续。对于 factorial()，当形参 n 等于 0 或 1 时，递归就结束了；
• 每次递归调用之后越来越接近这个限制条件。对于 factorial()，每次递归调用的实参为 n – 1，这会使得形参 n 的值逐渐减小，越来越趋近于 1 或 0。

更多关于递归函数的内容

factorial() 是最简单的一种递归形式——尾递归，也就是递归调用位于函数体的结尾处。除了尾递归，还有更加烧脑的两种递归形式，分别是中间递归和多层递归：

• 中间递归：发生递归调用的位置在函数体的中间；
• 多层递归：在一个函数里面多次调用自己。

递归函数也只是一种解决问题的技巧，它和其它技巧一样，也存在某些缺陷，具体来说就是：递归函数的时间开销和内存开销都非常大，极端情况下会导致程序崩溃。

更深阅读

17！程序结果溢出是什么原因 ？

[content_control]

例4.用递归法计算 n! 

unsigned long long int ff(int n)
{
   unsigned long long int f;
   if(n<0) printf("n<0,input error");
   else if(n==0||n==1) f=1;
   else f=ff(n-1)*n;
   return(f);
}
main()
{
   int n;
   unsigned long long int y;
   printf("\ninput a inteager number:\n");
   scanf("%d",&n);
   y=ff(n);
   printf("%d!=%lld",n,y);
}

把计算阶乘的递归函数的调用类型改为unsigned long long int 型，就能够计算出17，25等的结果。

[/content_control]

例5. 用户给出一个数，求出其相应的斐波那契数列数