函数的递归调用

在一个函数中直接或间接调用其函数本身叫做函数的递归调用,这是C语言的一大特色。例如下面这个求n!的数学函数:

当我们求一个数的阶乘时,可以将问题转化为n * (n - 1)!的问题,这样的话这个问题就转换成了一个经典的递归问题。例如我们要求fac(3):

   fac(3) = 3 * fac(2)
   fac(2) = 2 * fac(1)
   fac(1) = 1
   fac(2) = 2 * 1 = 2
   fac(3) = 2 * 3 = 6

这样就完成了整个递归算法。这里我们可以发现,所有递推式都可以化为递归。一个递归问题分为两个部分,分别是递推与回归。由已知的结果递推,推到有已知值的式子之后再向原方向回归,最后得知结果。又例如下面这个求斐波那契数列第n项的函数:

int  fib(int  n)
{
    if(n == 0)    return  0;
    if(n == 1)    return  1;
    if(n >1)    return  fib(n - 1) + fib(n - 2);
}

在求解过程中,求fib(n)的时候就要推到求解fib(n - 1)和fib(n - 2)的问题上,这样就又必须计算fib(n - 3)和fib(n - 4),以此类推,最后将会推到fib(1)和fib(0),能立即得到结果。这时候递推终止,再一路返回到fib(n)的值。这样看来,递归一定要有结束条件,否则就是一串无止尽的循环。 递归运算的优点是源程序简洁,缺点也很显著,会消耗过多的内存与运行时间,效率不高。

这本书是xt写的上次修改: 2019-04-18 15:36:33

results matching ""

    No results matching ""