递归

时间：2023-02-19 22:58:31

C函数允许函数调用它自己，这种调用过程称为递归。可以使用循环的地方通常都可以使用递归，有时使用循环解决问题好，但有时用递归更好。递归方案方案更简洁，但效率却没有循环高。

1.递归的基本原理

我们通过下面的程序来看看递归是如何工作的。

/* 递归示例 */
#include <stdio.h>
void recursion(int);

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

void recursion(int n){
    printf("第%d级递归：变量n的内存地址:%p\n", n, &n);
    if(n < 4)
        recursion(n + 1);
    printf("第%d级递归：变量n的内存地址:%p\n", n, &n);
    return;
}

/* 程序的运行结果如下：
第1级递归：变量n的内存地址:000000000061FE00
第2级递归：变量n的内存地址:000000000061FDD0
第3级递归：变量n的内存地址:000000000061FDA0
第4级递归：变量n的内存地址:000000000061FD70
第4级递归：变量n的内存地址:000000000061FD70
第3级递归：变量n的内存地址:000000000061FDA0
第2级递归：变量n的内存地址:000000000061FDD0
第1级递归：变量n的内存地址:000000000061FE00
*/

来分析一下程序中的递归是如何工作的。首先main()调用实参为1的recursion函数。进入函数recursion之后，由于n<4，函数会调用到第4级递归，此时n=4，执行第二个printf函数，得到输出内容”第4级递归：变量n的内存地址:000000000061FD70“，之后，执行return语句返回第3级调用，再执行第二个printf函数，以此类推，最后第1级调用运行结束，返回主调函数main()。注意，每级递归的变量都属于本级递归的私有变量，从内存地址也能看出。

我们可以这样理解，可以假设有一条函数调用链—res1()调用rea2()，res2调用res3()，res3()调用res4()。当res4()结束时，控制返回res3()，……，知道控制返回res1()。为了方便理解，数字表示几级递归，实际上，都是res函数。

2.递归和倒序计算

使用循环的地方通常可以使用递归，那么我们面临选择，究竟选择哪一个。一般而言，选择循环比较好。首先，每次递归都会创建一组变量，导致递归使用的内存更多，而且每次递归调用都会把创建的一组新变量放入栈中。递归调用的数量受限于内存空间。其次，由于每次递归调用都要花费一定的时间，所以递归的执行速度较慢。

那么什么时候使用递归比较好呢？递归处理逆序时非常方便，即处理的第一个值正好是最后一个打印的值。

/* 以二进制的形式打印一个整数 */
#include <stdio.h>
void to_binary(unsigned long)

int main(void){
    unsigned long n;
    while(scanf("%lu", &n) == 1){
        to_binary(n);
    }
    return 0;
}

void to_binary(unsigned long n)
{
    int r;
    r = n % 2;
    if(n >= 2)
        to_binary(n / 2);
    putchar(r == 0 ? '0' : '1');

    return;
}

3.递归的优缺点

递归既有优点也有缺点。优点是递归为某些编程问题提供了最简单的解决方案；缺点是一些递归算法会快速消耗掉计算机的内存资源，另外，递归也不方便阅读和维护。

/* 一个简单的递归程序 */
#include <stdio.h>
unsigned fib(unsigned n);

int main(void){
    fib(50);
    return 0;
}

unsigned fib(unsigned n)
{
    if(n > 2)
        return fib(n-1) + fib(n-2);
    else
        return 1;
}

相信大家学递归时，第一个接触的知识是斐波那契数列，该程序使用了双递归，即函数每一级递归都要调用本身两次。假如，像上述程序所给fib(50)。在第1级递归调用时，将创建一个变量n，在第2级递归时要分别创建两个变量n…以此类推，每一级的递归都会让变量的数量呈指数级增长，相信大家也知道棋盘放稻谷的例子，在指数增长中，即使很小的增长，也会让指数增长产生过大的数值，在本例中，指数增长的变量数量很快就会消耗掉计算机的大量内存，导致程序崩溃。

4.递归总结

第1，每级函数调用都有自己的变量。即每级递归的变量属于本级递归的私有变量，即使同一级的递归有两个变量n，它们都是不相同的。

第2，有几次函数调用就有几次函数返回。当且仅当（不考虑特殊情况）调用函数执行完毕之后，将控制全将传回上一级递归。

第3，递归函数位于递归调用之前的语句，均按与被调函数相同的顺序执行。

第4，递归函数位于递归调用之后的语句，均按与被调函数相反的顺序执行。

第5，虽然每级递归都有自己的变量，但是函数的代码是相同的，这涉及程序在计算机的存储，临时变量会被放在栈中，而代码段有专门的存放区。每次递归调用就相当于从头运行函数的代码。而除了为每次递归创建变量之外，递归调用非常相似于循环语句。实际上，有时递归与循环也能相互代替。

第6，递归函数必须包含能让递归调用停止的语句。为此，每次递归调用的形参都要使用不同的值。例如，在fib(n)调用fib(n-1)和fib(n-2)。

标签：

相关文章