物联网工程师之C语言递归

C语言允许函数调用自己本身，这种函数调用自身的情况被称为递归。递归是一种在程序设计中被广泛使用的算法，使用递归的方法可以把一个大型且复杂的问题层层简化成为一个与原问题相似的、规模较小的问题来求解。使用递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

6.1.1 递归的基本原理

递归是一种在数学中和计算机科学中都出现的一种思想，在这两个方面的定义如下：

1、数学中的递归。

在数学中最常见的例子是斐波纳契数列：

1 1 2 3 5 8 13 21 34 …

在这个数列中，从第三个数开始，后面的数等于它前面两个数相加之和。例如3 = 1 + 2，13 = 5 + 8。假定n是数列中的项的位置，这个数列的定义如下：

注意到在上述定义（斐波那契数列的递推公式）中，要计算f(n)的值，就要先计算f(n-1)和f(n-2)的值。可以把f(n)写成f(n - 1) + f(n - 2)，还可以进一步展开f(n – 1)和f(n – 2)，这样f(n)就等于(f(n – 3) + f(n – 2)) + (f(n – 4) + f(n – 3))，当然还可以继续向下展开。

在数学中这种想要计算函数自身的值，仍然要通过这个函数自身来计算另一个值的情形，被称为递归。

2、编程语言中的递归

在编程语言中，递归是指一个函数直接或间接调用自己本身，这种函数称为递归函数。

C语言允许函数的递归调用。在递归调用中，调用者和被调用者是同一个函数。执行递归函数将反复调用其自身，每调用一次就进入新的一层。示意图见图6-28：

图 628 递归调用流程图

上面的流程图展示了一个不断调用自身的函数foo。直接将上面的流程图写成程序，如例6-28所示：

例628 无限递归的程序

• void foo()
  {
  int n;
  foo();
  }
  int main()
  {
  foo();
  }

但是上面的递归调用存在一个问题……是的，这个递归没有终止条件！函数foo是一个递归函数，但是运行该函数将无休止地调用自身，这将导致程序陷入死循环并引发严重问题。

运行上面的程序会发生如下问题，如图6-29：

由于程序无限制的调用自己，导致栈空间耗尽，所以程序崩溃了。

如果想要实现一个正确的递归函数，应该具有下面三个条件：

• 递归边界条件，即边界条件即终止递归调用的条件。
• 递归前进处理功能，即如果进行递归的话，将要执行的语句。
• 递归返回处理功能，即如果不再进行递归，从控制流程从函数返回的语句。

通常递归边界条件的实现方法是使用条件判断，当边界条件不满足时，递归前进；当边界条件满足时，递归返回。处理流程图如图6-  所示：

图6-  递归的处理流程图

按照递归的处理流程，将例6-28的无限递归程序简单修改一下，就可以得到一个一定能够终止的递归程序了。为了展示递归的原理，程序中增加了一些说明文本，如例程6-29所示：

例 629 有限递归程序（递归十次后结束递归）

• #include <stdio.h>
  void foo(int depth)
  {
  int n;
  if(depth == 10)/*递归边界条件，当递归深度达到10时，不再进行递归操作*/
  {
  /*递归返回处理功能*/
  return;
  }
  else
  { /*递归前进处理功能*/
  printf("将要进行第 %d 层调用。\n", depth + 1);
  foo(depth + 1);
  printf("从第 %d 层调用中返回。\n", depth + 1);
  }
  }
  int main()
  {
  printf("将要进行第 %d 层调用。\n", 1);
  foo(1);
  printf("从第 %d 层调用中返回。\n", 1);
  }

程序的运行结果如图6-30所示：

图 630 有限递归程序

例程6-29为无限递归程序提供了结束递归的条件：函数foo每进行一次递归，就为变量depth加1；当递归到第十层时（此时depth等于10）停止递归，直接返回，如程序中五至八行所示。增加了结束递归的条件之后，递归就不会无休止地进行下去了。

通过例6-29，我们初步了解了怎样实现递归函数，下面结合这个例程来介绍递归的基本原理，具体要点如下。

• 递归调用是分级的（图6-31）。对于例6-29中的递归函数foo而言，第一次调用被称为第一级调用，第二次调用被称为第二级调用，以此类推。

  

  图 631 递归调用的分级

  • 每一级递归函数都有自己的局部变量，互相之间是不能相互访问的（图6-32）。以例6-28的无限递归函数foo为例，第一级递归中的变量n和第二级递归中的变量n没有任何关系；虽然它们的变量名都是n，但是它们是相互独立的，可能具有不同的值。

    

    图 632 不同级别之间的递归调函数有不同的局部变量

    • 每一次递归调用都有一次对应的返回。每一级调用只能返回到上一级调用者那里，无法一次返回多层，也不能直接返回到主函数。
    • 递归函数中，位于递归调用之前的语句是逐级顺序执行的，而位于递归调用之后的语句是逐级逆序执行的。如例6-29中，在第十三行递归调用之前，输出的是“将要进行第1层调用”、“将要进行第2层调用”直到“将要进行第9层调用”，与递归函数的执行顺序相同；而第十四行的语句位于递归调用之后，输出的是“从第9层调用中返回”、“从第8层调用中返回”直到“从第1层调用中返回”，与递归函数的执行顺序相反，但与递归函数的返回顺序相同。
    • 递归函数中必须包含可以终止递归调用的语句或条件。一般而言，递归函数中会使用条件判断语句判断当前是否到达了结束递归的条件，若条件满足，则不再继续进行递归，由此递归调用被中止。如在例6-2中，第六行程序判断了递归的级别（或称层次、深度）是否为第十级后，到达第十级后不再继续递归调用，这意味着递归只能进行十次，十次后即终止。

     

    M脚下留心：

    在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以不宜用递归解决层次过多的问题。另外递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。

    6.1.1 递归的应用：计算阶乘

    一个整数的阶乘被定义为这个整数到1的乘积。使用公式表示如下：

    对于整数N，N的阶乘。

    特别地，0的阶乘等于1。

    为计算一个数的阶乘，最简单的实现方法是通过循环来实现。不过也可以使用递归来完成运算。下面给出一个使用递归进行阶乘运算的例子，如例6-30所示。

    例630 使用递归计算阶乘

    • #include <stdio.h>
      long long factor(int n)
      {
      long long ret;
      if(n == 0)
      {
      return 1;
      }
      else
      {
      ret = n * factor(n - 1);
      return ret;
      }
      }
      int main()
      {
      long long ret = factor(20);
      printf("20! = %lld\n", ret);
      }

    程序运行后的结果如图6-33所示

    

    图 633 使用递归计算阶乘

    程序中使用了long long int型变量以存储计算结果，这是因为阶乘运算的结果往往很大，使用long long int可以在一定范围内避免计算结果的溢出。

    为什么可以使用递归来实现阶乘运算呢？这是因为对于阶乘运算而言，还有如下的性质：

     

    由于(N-1)!是(N-1)到1的所有整数的乘积，将这个结果再乘以N自然就是N的阶乘了。放在程序中，就有

    factor(n) = n * factor(n - 1);

    这意味着计算N的阶乘的问题可以被化为一个较小规模的问题——计算(N - 1)的阶乘，而计算(N - 1)的阶乘又可以被化为一个较小规模的问题——计算(N - 2)的阶乘……以此类推。直到最后N = 0时，factor(N) = 1，递归结束。N = 0就是这次递归运算的结束条件。

     

    :动手体验：

    请使用循环来实现计算n的阶乘的程序。

    例如，所要求的数是4，则阶乘式是1*2*3*4,得到的积是24，24就是4的阶乘。如果所要求的数是6，则阶乘式是1*2*3*```*6,得到的积是720，720就是6的阶乘。如果所要求的数是n,则阶乘式为1*2*3*```*n,设得到的积是x,x就是n的阶乘。

    阶乘运算既可以使用循环实现，又可以使用递归实现，到底哪种实现方式更好呢？一般而言，如果一个操作可以同时使用循环和递归实现的话，应该优先选择使用循环的实现方式。这是因为递归会消耗更多的栈空间，每一级递归的函数调用也会消耗额外的时间。

    6.1.1 递归的应用：进制转换

    首先回顾一下第二章中讲过的将十进制数转换为二进制数的方法——除二取余法：把给定的正整数不断除以2，将每次得到的余数连起来再逆序，就是对应的二进制表示。以十进制的13为例：

     

    操作步骤	被除数	除2后的商	余数
    1	13	6	1
    2	6	3	0
    3	3	1	1
    4	1	0	1

     

    由上可知，13的二进制表示就是1101。

    与阶乘计算相同，除二取余法也是不断地把一个较大规模的问题转换成一个稍小规模的问题（每次n都是上一次运算时的1/2）。注意到最后的二进制表示是逆序输出的，恰好和递归的返回顺序一致（也就是递归函数中递归调用之后的语句的执行顺序）。这两点启发大家使用递归实现这一功能。

    例6-31展示了如何使用C语言进行十进制数转换为二进制数的工作。

    例631 使用递归进行进制转换

    • #include <stdio.h>
      void convert(int n)
      {
      if(n == 0)
      {
      printf("0");
      }
      else if(n == 1)
      {
      printf("1");
      }
      else
      {
      int mod = n % 2;
      convert(n / 2);
      printf("%d", mod);
      }
      }
      int main()
      {
      int dec;
      printf("请输入要转换的十进制正整数或0：");
      scanf("%d", &dec);
      printf("转换后的结果是：");
      convert(dec);
      printf("\n");
      }

    程序的运行结果如图6-34所示：

    

    图 634 使用递归进行进制转换

    递归函数convert中，递归结束的条件有两个，分别是n == 1和n == 0。n为1时，意味着只要输出1作为转换后的二进制数最高位即可，转换可以到此结束；而n为0时，则必须输出一个“0”作为转换后的结果。

    • 本章小结

    本章详细介绍了C语言中有关函数的点点滴滴，包括函数的定义和声明、变量的作用域、局部变量和全局变量的异同等等，并介绍了递归调用的有关知识。此外还对模块化编程做了基础性的介绍。本章依然是C语言的知识基础，希望大家能在学习之后进行巩固训练，以牢固掌握该部分内容。