递归之详解

C允许一个函数调用其本身。这种调用过程被称作递归(recursion)。递归有时很难处理,而有时却很方便实用。当一个函数调用自己时,如果编程中没有设定可以终止递归的条件检测,它会无限制地进行递归调用,所以需要进行谨慎处理。

递归一般可以代替循环语句使用。有些情况下使用循环语句比较好,而有些时候使用递归更有效。递归方法虽然使程序结构优美,但其执行效率却没有循环语句高。

递归的使用

为了具体说明,请看下面的例子。程序代码 1 中函数 main( ) 调用了函数 up_and_down( ),我们把这次调用称为“第一级递归”。然后 up_and_down ( ) 调用其本身,这次调用叫做“第二级递归”。第二级递归调用第3级递归,依此类推。例子中共有4级递归。为了深入其中看看究竟发生了什么,程序不仅显示了变量 n 的值,还显示出了储存 n 的内存地址 &n
/ 程序代码 1/

#include <stdio.h>

void up_and_down (int);

int main (void)
{
        up_and_down (1);
        return 0;
}

void up_and_down (int n)
{
    printf("Level %d:n location %p\n",n,&n);/* 1 */ 
    if(n &lt; 4)
        up_and_down(n + 1);
    printf("Level %d:n location %p\n",n,&n);/* 2 */
}

输出结果

Level 1:n location 0×0012ff48
Level 2:n location 0×0012ff3c
Level 3:n location 0×0012ff30
Level 4:n location 0×0012ff24
Level 4:n location 0×0012ff24
Level 3:n location 0×0012ff30
Level 2:n location 0×0012ff3c
Level 1:n location 0×0012ff48

我们来分析程序中递归的具体工作过程。首先 main() 使用参数 1 调用了函数 up_and_down ()。于是 up_and_down () 中形参量 n 的值为 1 ,故打印语句#1 输出了Level 1。然后,由于 n 的数值小于 4, 所以 up_and_down () (第 1 级)使用参数 n+1 即数值 2 调用了 up_and_down () (第 2 级)。这使得 n 在第 2 级调用中被赋值 2,打印语句 #1 输出的是 Level 2。与之类似,下面的两次调用分别打印出 Level 3 和 Level 4。

当开始执行第 4 级调用时,n的值是4,因此 if 语句的条件不满足,这时不再继续调用 up_and_down () 函数。第 4 级调用截止执行打印语句#2,即输出 LEVEL 4,因为 n的值是4。现在函数需要执行 return语句,此时第 4 级调用结束,把控制返回给该函数的调用函数,也就是第 3 级调用函数。第 3 级调用函数中前一个执行过的语句是在if 语句中进行第 4 级调用。因此,它开始举行执行其后续的代码,即执行打印语句#2,折将会输出 LEVEL 3。当第 3 级调用结束后,第 2 级调用函数开始继续执行,即输出了LEVEL 2。依此类推

注意,每以及的递归都使用它自己私有的变量 n。你可以通过查看地址的值来得出这个结论(当然,不同的系统通常会以不同的格式显示不同的地址。关键点在于,调用时的 Level 1地址和返回时的 Level 1地址是相同的)。

如果你对此感到有些迷惑,可以假想进行了以系列函数调用,即使用 fun1 () 调用 fun2 () 、fun2 () 调用 fun3 (),fun3 () 调用 fun4 ()。fun4 () 执行完后,fun3 () 会继续执行。而 fun3 () 执行完后开始继续执行 fun2 (),最后 fun2 () 返回到fun1 () 中并执行后续代码。递归过程解释如此,只不过fun1 ()、fun2 ()、fun3 () 和 fun4 () 是相同的函数。

递归的基本原理

刚接触递归可能会感到迷惑,下面将讲述几个基本要点以便理解该过程。

第一,每一级的函数调用都有自己的变量,也就是说,第 1 级调用中的 n 不同于第 2 级调用中的 n,因此程序创建了 4 个独立的变量,虽然每个变量的名字都是 n,但是它们分别具有不同的值。当成最终返回到对 up_and_down () 的第 1 级调用时,原来的 n 仍具有初始值 1 (请参见图)。

第二,每一次函数调用都会有一次返回。当程序流执行到某一级递归的结尾处时,它会转移到前第 1 级递归继续执行。程序不能直接返回到 main ()中的初始调用部分,而是通过递归的每一级逐步返回,即从 up_and_down () 的某一级递归返回到调用它的那一级。

第三,递归函数中,位于递归调用前的语句和各级被调函数具有相同的执行顺序。例如,在程序代码 1 中,打印语句#1 位于递归调用语句之前。它安装递归调用的顺序被执行了4 次,即依次为第 1 级、第 2 级、第 3 级和第 4 级。

第四,递归函数中,位于递归调用后的语句的执行顺序和各个被调函数的顺序相反。例如,打印语句#2 位于递归调用语句之后,其执行顺序是:第 4 级、第 3 级、第 2 级和第 1 级。递归调用的这种特性在解决涉及反向顺序的编程问题时很有用。下文中将给出这样的一个例子。

第五,虽然每一级递归都有自己的变量,但是函数代码并不会得到复制。函数代码是一系列的计算机指令,而函数调用就是从头执行这个指令集的一条命令。一个递归调用会使程序从头执行相应函数的指令集。除了为每次调用创建变量,递归调用非常类似于一个循环语句。实际上,递归有时可被用来代替循环,反之亦然。

最后,递归函数中必须包含可以终止递归调用的语句。通常情况下,递归函数会使用一个 if 条件语句或其他类似的语句以便当函数参数达到某个特定值是结束递归调用。比如正上例中,up_and_down (n) 调用了 up_and_down (n+1),最后实际参数的值达到 4 时,条件语句 if (n < 4) 得不到满足,从而结束递归。

尾递归

最简单的递归形式是把递归调用语句放在函数结尾即恰在 return 语句之前。这种形式被称为尾递归(tailrecursion)或结尾递归(end recursion),因为递归调用出现在函数尾部。由于尾递归的作用相当于一条循环语句,所以它是最简单的递归形式。

下面我们讲述分别使用循环和尾递归完成阶乘计算的例子。一个整数的阶乘就是从 1 到该数的乘积。例如,3 的阶乘(写作3!)是1×2×3。0!等于 1,而且负数没有阶乘。程序代码 2 中,第一个函数使用 for 循环计算阶乘,而第二个函数用的是递归方法。

/* 程序代码 2*/
// factor.c -- 使用循环和递归计算阶乘
#include <stdio.h>

long fact (int n);
long rfact (int n);

int main (void)
{
    int num;

    printf("This program calculates factorials.\n");
    printf("Enter a value in the range 0-12 (q to quit):\n");
    while(scanf ("%d",&num) == 1)
    {
        if (num &lt; 0) printf("No negative numbers. please.\n"); else if(num > 12)
            printf("Keep input under 13.\n");
        else
        {
            printf("loop: %d factorial = %ld\n",unm,fact(num));
            printf("recursion:%d factorial = %ld\n", num,rfact(num));   
        }
        printf("Enter a value in the range 0-12 (q to quit):\n");
    }
    printf("Bye.\n");
    return 0; 
}
long fact(int n)// 使用循环计算阶乘
{
    long ans;
    for(ans = 1; n < 1; n--)
        ans *=n;
    return ans;
}

long rfact(int n) //使用递归计算阶乘
{
    long ans ;
    if(n > 0)
        ans = n * rfact (n-1);
    else
        ans = 1;
    return ans;
}

用来测试的驱动程序把输入限制在整数 0 到 12 之间。因为 12! 稍大于 5 亿,而 13! 比我们的程序中的long 类型数据大得多,所以如果计算 13! 的阶乘,就必须使用范围更大的数据类型,比如 double 类型或 long long 类型。

下面运行示例

This program calculates factorials.
Enter a value in the range 0-12 (q to quit):
5
loop: 5 factorial = 120
recursion: 5 factorial = 120
Enter a value in the range 0-12 (q to quit):
10
loop: 10 factorial = 3628800
recursion: 5 factorial = 3628800
Enter a value in the range 0-12 (q to quit):
q
Bye.

使用循环方法的函数吧 ans 初始化为 1 ,然后将其依次和从 n 到 2 依次递减的整数相乘。根据公式, ans 还应该和 1 相乘,但这并不会改变结果。

下面我们研究使用递归方法的函数,其中关键的一点是 n! = n×(n-1)!。因为 (n-1)!是 1 到 n-1 的所有正数之积,所以该数乘以 n 就是 n 的阶乘。这也暗示了可以采用递归的方法。调用函数 rfact () 时,(n) 就等于n×rfact(n-1)。这样就可以通过调用 rfact(n-1)来计算 rfact(n),如程序代码 2 中所示。当然,递归必须在某个地方结束,可以在 n 为 0 时把返回值设为 1,从而达到结束递归的目的

在程序代码 2 中,两个函数的输出结果相同。虽然对 rfact() 的调用不是函数中的最后一行,但它是在 n>0 的情况下执行的最后一条语句,因此这也属于尾递归。

既然循环和递归都可以用来实现函数,那么究竟选择哪一个呢?一般来讲,选择循环更好一些。首先,因为每次递归调用都拥有自己的变量集合,所以就需要占用较多的内存;每次递归调用需要把的变量集合存储躲在堆栈中。其次,由于进行每次函数调用需要花费一定的时间,所以递归的执行速度较慢。既然如此,那么我们为什么还要讲述以上例子呢?因为尾递归是最简单的递归形式,比较容易理解;而且在某些情况下,我们不能使用简单的循环语句代替递归,所以就有必要学习递归的方法。

递归和反向计算

下面我们考虑一个使用递归处理反序的问题(在这类问题中使用递归比使用递归更简单)。问题是这样的:编写一个函数将一个整数转换成二进制形式。二进制形式的意思是指数值以 2 为底数进行表示。例如 234 在十进制下表示为 2×102+3×101+4×100,而二进制 101 意思是 1×22+0×21+1×20。二进制数只使用数字 0 和 1 表示。

解决上述问题,需要使用一个算法(algorithm)。例如,怎样得到 5 的二进制数表示?因为奇数的二进制形式的最后一位一定是 1,而偶数的二进制的最后一位是 0,所以可以通过计算 5%2 得出 5 的二进制形式中最后一位数字是 1 或者 0 。一般来讲,对于数组 n,其二进制的最后一位是 n%2 ,因此计算出的第一个数字恰是需要输出的最后一位数字。这就需要使用一个递归函数实现。在函数中,首先在递归调用之前计算 n%2 的数值,然后在递归调用语句之后进行输出。这样,计算出的第一个数值反而在最后一个输出。

为了得出下一个数字,需要把原数组除以 2。这种计算就相当于在十进制下把小数点左移一位。如果此时得出的数值是偶数,则下一个二进制的数值是 0;若得出的数值为奇数,则下一个二进制位的数值就是 1.liru ,5/2的数值是 2(整数除法),所以下一位值是 0。这时已经得到了数值 01。重复上述计算,即使用 2 除以 2 得出 1,而 1%2 的数值是 1,因此下一位值是 1。这时得到的数值101。那么何时停止这种计算呢?因为只要被 2 除的结果等于或大于 2,那么就还需要一位二进制进行表示,所以只有被 2 除的结果小于 2 时才停止计算。每次除以 2 就可以得出一位二进制位值,直到计算出最后一位为止(如果读者对此感到不解,可以在十进制下做类似的运算。628 除以 10 的余数是 8 ,因此 8 就是最后一位。上步计算的商是62,而 62 除以10 的余数是 2,所以 2 就是下一位值,依此类推)。在程序代码 3 中实现了上述算法。

/* 程序代码 3*/
// binary.c --以二进制形式输出整数
#include <stdio.h>

void to_binary (unsigned long n);

int main(void)
{
    unsigned long number;
    printf("Enter an integer(q to quit):\n");
    while(scanf("%ul",&amp;number) == 1)
    {
        printf("Binary equivalent:");
        to_binary(number);
        putcher("\n");
        printf("Enter an integer (q to quit):\n");
    }
    printf("Done.\n");

   return 0;
}
void to_binary(unsigned long n)/* 递归函数 */
{
    int r;
    r = n %  2;
    if(n &gt;= 2)
        to_binary(n / 2);
    putcher('0' + r);

    return;
}

以上程序中,如果 r 是 0,表达式‘0’+r 就是字符‘0’;当 r 为 1 时,则该表达式的值为字符‘1’。得出这种结果的前提假设是字符‘1’的数值编码比字符‘0’的数值编码大 1。ASCII 和 EBCDIC 两种编码都满足上述条件。更一般的方式,你可以使用如下方法:
putchar(r ? '1' : '0');
下面是一个简单的运行示例:

Enter an integer(q to quit):
9
Einary equivalent:1001
Enter an integer (q to quit):
255
Einary equivalent:11111111
Enter an integer (q to quit):
1024
Einary equivalent:10000000000
Enter an integer (q to quit):
q
Done.

当然,不使用递归也能实现这个算法。但是由于本算法先计算出最后一位数值,所以在显示结果之前必须对所有的数值进行存储(比如放在一个数组之中)。

递归的优缺点

使用递归既有优点也有缺点。其优点在于为某些编程问题提供了最简单的解决方法,而缺点是一些递归算法会很快好紧计算机的内存资源。同时,使用递归的程序难于阅读和维护。从下面的例子中可以看出使用递归的优缺点。

斐波那契数列定义如下:第一个和第二个数字都是 1,而后续的每个数字是其前两个数字之和。例如,数列中前几个数字是 1、1、2、3、5、8和 13.斐波那契数列在数学上很受重视,甚至有专门的刊物讨论它。下面我们创建一个函数,它接受一个正整数 n作为参数,返回相应的斐波那契数值。

首先,关于递归深度,递归提供了一个简单的定义。如果调用函数 Fibonacci() ,当 n 为 1或 2 时 Fibonacci(n) 应返回 1;对于其他数值应返回 Fibonacci(n-1)+Fiboncci(n-2);

long Fiboncci(int n)
{
    if( n &gt; 2)
        return Fiboncci(n-1) + Fiboncci(n-2);
    else
        return 1;
}

这个C 递归函数只是重述了递归的数学定义(为使问题简化,函数不处理小于 1 的数值)。同时本函数使用了双重递归(double recursion);也就是说,函数对本身进行了两次调用。这就会导致一个弱点。

为了具体说明这个弱点,先假设调用函数 Fibonacci(40)。第 1 级递归会创建变量 n。接着它两次调用Fibonacci(),在第 2 级递归中又会创建两个变量 n。上述的两次调用中的每一次又进行了两次调用,因而在第 3 级调用中需要 4 个变量 n,这时变量总数为 7.因为每级调用需要的变量数是上一级变量数的 2 倍,所以变量的个数是以指数规律增长的!这种情况下,指数增长的变量数会占用大量内存,这就可能导致程序瘫痪。

当然,以上是一个比较极端的例子,但它也表明了必须小心使用递归,尤其是当效率处在第一位的时候。

来自 C Primer Plus(第五版)修改部分内容。