【C语言深度剖析】深入理解C语言中函数的递归算法

文章目录

- 定义
- 难点
- 举例说明
- - 例题一
  - 例题二
- 总结

定义

递归： 一个函数在它的函数体内调用它自身，这种调用过程称为递归，这种函数称为递归函数

在递归调用中，主调函数又同时是被调函数。执行递归函数将反复调用其自身，每调用一次就进入新的一层

难点

运行递归函数将无休止地调用其自身，这当然是不正确的！

为了防止递归调用无终止的进行，就必须在函数内有终止递归的条件判断语句，满足某种条件后就不再作递归调用，然后逐层返回！！！

这也是递归不易理解的一个难点！

举例说明

我这里通过举例来说明这个递归是如何使用的吧

例题一

接受一个整型值（无符号），按照顺序打印它的每一位。
例如：
输入：1234，输出 1 2 3 4

代码如下：

#include <stdio.h>

void Print(unsigned int n)
{
    if (n > 9)
    {
        Print(n / 10);
    }
    printf("%d ", n % 10);
}

int main()
{
    unsigned int num = 0;
    scanf("%u", &num);
    
    Print(num);

    return 0;
}

分析：

我这里画了一个图，配合下面的解析看，如图：（红色表示递，绿色表示归）

当我们走到主函数里面的时候，我们先输入一个数字：123，那么num = 123

然后就调用我们的Print(num)函数，此时我们就叫做递出去

图A：

所以此时的图A当中的n = 123，然后判断if语句：123 > 9为真，进入内部，然后调用Print(n / 10)函数
这次调用的Print函数就走到了图B，此时我们传进去的就是：123 / 10 的结果，也就是12

图B：

所以图B中的n = 12，然后判断if语句：12 > 9为真，进入内部，那么又要调用Print(n / 10)函数
这次调用的Print的函数就走到了图C，此时我们传进去的就是：12 / 10 的结果，也就是1

图C：

所以图C中的n = 1，然后判断if语句：1 > 9为假，所以直接执行print语句，1 % 10 = 1，那么就会在屏幕上打印1和空格

图B：

此时我们图C中的函数已经调用完了，那么就要回归到图B函数中，执行图B中的printf语句，而图B中的n = 12
那么12 % 10 = 2，然后打印2和空格

图A：

此时我们又要从图B回归到图A，执行图A中的printf语句，而图A中的n = 123，那么123 % 10 = 3，然后打印3和空格

主函数：

图A函数执行完以后，又要回归到我们的主函数Print(num)，此时我们的函数调用任务已经结束了，屏幕打印输出：1 2 3

这就是递归的过程，递出去，归回来，

例题二

我们再来做一个题检验一下！

有5个学生在一起
问第五个学生多少岁？他说他比第四个学生大2岁；
问第四个学生多少岁？他说比第三个学生大2岁；
问第三个学生多少岁？他说比第二个学生大2岁；
问第二个学生多少岁？他说比第一个学生大2岁；
最后问第一个学生，他说是10岁。
请问第5个学生多少岁？

这里的话我们用递归的思想来做这道题

思考

age(5) = age(4) + 2;
age(4) = age(3) + 2;
age(3) = age(2) + 2;
age(2) = age(1) + 2;
age(1) = 10;

用数学公式表达如下：

    age(n)= 10; (n = 1)

    age(n)= age(n-1) + 2；(n > 1)

可以看到，当n >1时，求第n个学生的年龄的公式是相同的

因此可以用一个函数表示上述关系。如图表示求第5个学生年龄的过程

显然，这是一个递归问题

由图所示，求解可分为两个阶段：

第1阶段是回溯，即将第n学生的年龄表示为第（n-1）个学生的函数，而第（n-1）个学生的年龄仍然还不知道，还要回溯到第（n-2）个学生的年龄……直到第一个学生的年龄。此时age(1)已知，不必再向前推了。

然后开始第二阶段，采用递归方法，从第一个学生的已知年龄推算出第二个学生的年龄(12岁)，从第二个学生的年龄推算出第三个学生的年龄(14岁)……一直推算出第5个学生的年龄(18岁)为止。

也就是说，一个递归的问题可以分为回溯和递归两个阶段。要经历若干步才能求出最后的值。显而易见，如果要求递归过程不是无限制进行下去，必须具有一个结束递归过程的条件。

本例中，age(1)=10,就是使递归结束的条件。

代码如下：

#include <stdio.h>

int age(int n)
{
    int c = 0;
    if (n == 1)
    {
        c = 10;
    }
    else
    {
        c = age(n - 1) + 2;
    }
    return c;
}
int main()
{

    int stu = 0;
    stu = age(5);
    printf("第五个学生的年龄为: %d\n", stu);
    return 0;
}