一，递归概念

在讲解之前，我们先先来看一段代码：

int main()
{
    printf("hehe\n");
    main();
    return 0;
}

此代码是典型的栈溢出，但不妨碍我们理解函数递归概念。main函数内部再次调用了main函数，用printf函数体现一下该函数的调用过程。

       不难看出，这是一个死循环程序，本质是main函数的自我反复调用，而又没有限制条件，才会反复进行，这就是函数的递归。

       简单来说，函数递归实质上就是函数的自我调用，每一次函数调用，都会在内存的栈区申请一块空间，以此来保证函数的正确调用和返回。但是函数不能无限递归下去，会出现栈溢出现象。

递就是递推，归就是回归，二者作用后会把大事化小，复杂问题简单化。

 

       递归限制条件：

1，当满足某个限制条件的时候，递归便不再继续调用。

2，每次递归调用越来越接近这个限制条件。

       （这个限制条件又叫跳出条件）

 

接下来，我们用几个例子来深入了解一下递归。

 

二，递归举例

 

1，求n的阶乘

1到n的数字累积相乘，不考虑溢出，可以在主函数中调用阶乘函数，然后在返回值上再次调用自定义函数，再加限制条件让运算无限的靠近这个跳出条件。

n的阶乘有如下规律：

n! = n * ( n - 1)!

5! = 5 * 4!

4! = 4 * 3!

…

1! = 1

其中，0的阶乘为1。

int fac(int n)
{
    if (n == 0)
        return 1;
    else
        return fac(n - 1) * n;
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int i = fac(n);
    printf("%d\n", i);
    return 0;
}

       在主函数中调用阶乘函数，然后在返回值上再次调用自定义函数，再加限制条件让运算无限的靠近这个跳出条件。

       比如在控制台上输入n=10，以此求10的阶乘，那么，自定义函数会反复的自我调用，n如果不等于0，会一直返回类似10*9！，9*8！，8*7！这样的形式，再赋值给i，直到n从10被减为0，自定义函数返回1，跳出递归。

 

        接下来，我们一步一步分析，当输入n = 10，fac(10) = fac(9) * 10; 自定义函数中n又会变成9，并再次执行fac(n - 1) * n即为 fac(9) =  fac(8) * 9, 以此类推fac(8) = fac(7) * 8,  fac(7) = fac(6) * 7等。当算到fac(1) = fac(0)*1时，由于限制条件，fac(0)直接等于1，接下来在一步一步往回带，可以叫做回归。

fac(10) = fac(9) * 10

fac(9) = fac(8) * 9

fac(8) = fac(7) * 8

fac(7) = fac(6) * 7

...

fac(1) = fac(0)*1

fac(0) = 1

推出限制条件处的最终值fac(0)，此为递推；把fac(0)，fac(1)，往回带算出fac(10)，此为回归。

 

2，求第n个斐波那契数

 

我们在中学阶段学习过斐波那契数列，形如“1,1,2,3,5,8,13,21,34,55... ...”。

      简单理解，从第三个数开始，该位数字为前两个数字之和，以此递推到无穷大。那么，我们要通过递归来实现求第n个斐波那契数是什么。

       从第三个数开始，先假设n>2，那么第n个斐波那契数等于第（n - 1）个斐波那契数 + 第（n - 2）个斐波那契数，如果n<2，直接返回值为1即可。

int fib(int n)
{
    if (n > 2)
        return fib(n - 1) + fib(n - 2);
    else
        return 1;
}
int main()
{
    int n = 0;
    scanf("%d", &n);
    int m = fib(n);
    printf("%d\n", m);
    return 0;
}

      需要注意的是，该案例运用递归会造成大量的重复计算，如果要求n的值过大，计算机计算的时间非常长，（如n = 50），fib函数的自我调用会像细胞分裂一样延伸。

 

假设n = 40，我们检查一下在这样的递归下n = 3究竟被计算了多少次。引入全局变量count

检验：
int count = 0;
int fib(int n)
{
    if (n == 3)
        count++;
    if (n > 2)
        return fib(n - 1) + fib(n - 2);
    else
        return 1;
}
int main()
{
    int n = 0;
    scanf("%d", &n);
    int m = fib(n);
    printf("%d\n", m);
    printf("count = %d\n", count);
    return 0;
}
 

   

这个数字证明了一切。

 

既然递归这个方法不好用了，为什么非要钻牛角尖呢？我们可以用迭代（循环）的方式实现代码:

1,  1,  2,  3,  5,  8,  13,  21,  34,  55

a   b   c

      a   b   c

            a   b   c

     

     引入三个变量，以循环的方式多次赋值，其中每循环一次进行一次赋值，即a = b, b = c, 

再c = a + b。

下面是完整代码：

int fib(int n)
{
    int a = 1;
    int b = 1;
    int c = 1;
    int i = 0;
    if (n > 2)
    {
        for (i = 3; i <= n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
    }
    return c;
}
int main()
{
    int n = 0;
    scanf("%d", &n);
    int m = fib(n);
    printf("%d\n", m);

    return 0;
}

其中n<2的情况在这段代码中可以不用考虑了，因为初始化c = 1，符合实际。

 

我们来一道简单的题目做个收尾：

 

3，顺序打印一个多位数的各项数字

在之前，我们学习了倒序打印多位数n，n%10，n/10即可得到。如1234，先取模10在除以10，即可得到4,3,2,1。

在学习了递归之后，可以顺序打印：

void Print(int n)
{
    if (n > 9)//当n不满足此条件时，将结束Print函数自我调用，从此时开始进行打印
        Print(n / 10);
    printf("%d ", n % 10);
}

int main()
{
    int n = 0;
    scanf("%d", &n);//1234
    Print(n);
    return 0;
}

     我们首先要保证n的位数大于等于2，即n>=9，以此作为跳出条件。递归的特点是，函数的自我调用到最后是再回返回数值。在这段代码中，会先进行到最大位，再从最大位回归，即先打印最大位，实现顺序打印。

 

这些便是递归的思想，就是通过少量的代码，完成重复运算。
 

 

感谢阅读！