【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;}

总结

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量

递归的主要思考方式在于： 把大事化小