C-递归

递归这个词，生活中应该比较少用到，你可能对它比较陌生，而本文的主题就是它。举个从小就听过的例子：从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山，山里有座庙...

再举个例子，下图就可以看做近似的递归，


再来看一下百度对递归词汇的解释，


相信通过上面的解释，大家对递归有一定的认识了。接下来，我们正式来讲讲程序设计中的递归函数。

递归函数就是函数直接或者间接调用自身的函数。许多教科书把阶乘运算用来说明递归，这是非常不幸的。因为这个时候使用，它的效率非常之低。

这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数转换为可打印的字符形式。例如，给出一个值4267，我们需要依次产生字符'4'、'2'、'6'、'7'。

我们采用的策略是把这个值反复对10取余得到余数处理打印后，并除以10。例如，4267除10的余数是7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字'7'的值。在ASCII码中，字符'7'的值是55，所以我们需要在余数上加上48来获得正确的字符。但是，使用字符常量而不是整型常量可以提高程序的可移植性。考虑下面的关系：

'0' + 0 = '0'

'0' + 1 = '1'

'0' + 2 = '2'

从这些关系中，我们很容易看出在余数上机上'0'就可以产生对应字符的代码。接着就打印出余数。下一步是取得商，4267/10等于426（整型取整）。然后用这个得到的值重复上述步骤。

这种处理方法存在的问题是它产生的数字次序正好相反，它们是逆向打印的。在下面的程序中，我们就用递归来修正这个问题。

void binary_to_ascii(unsigned int value)

{

  unsigned int quotient = value / 10;

  if (quotient !=0)

    binary_to_ascii(quotient);

    putchar(value % 10 + '0');

}

上面程序中的函数是递归性质的，因为它包含了一个对自身的调用。乍一看，函数似乎永远也不会终止，当函数调用时，它将调用自身，第二次调用还是调用自身，以此类推，似乎永远调用下去。但是，事实上并不会出现这种情况。

这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不再调用自身。

该程序中，递归函数的限制条件就是变量quotient为0。在每次递归调用之前，我们都把quotient除以10，所以每递归一次，它的值就更接近0。当它最终变成0时，递归便告终了。

那么我们再来分析下，递归是如何帮我们以正确的顺序打印这些字符的呢？下面是这个函数的工作流程。

1.将参数值除以10

2.如果quotient的值为非零，调用binary_to_ascii打印quotient当前值的各位数字

3.接着，打印步骤1中取余运算的余数

注意在第二个步骤中，我们要打印的是quotient当前值的各位数字。我们所面临的问题和最初的问题完全相同，只是变量quotient的值变小了。我们用刚刚编写的函数（把整数转换为各个数字字符并打印出来）来解决这个问题。由于quotient的值越来越小，所以递归最终会终止。

一旦你理解了递归，阅读递归函数最容易的方法不是纠缠于它的执行过程，而是相信递归函数会顺利完成它的任务。如果你的每个步骤正确无误，你的限制条件设置正确，并且每次调用之后更接近限制条件，递归函数总是能够正确地完成任务。

追踪递归函数

为了理解递归的工作原理，你需要追踪递归调用的执行过程，所以让我们来进行这项工作。追踪一个递归函数执行过程的关键是理解函数中所声明的变量是如何存储的。当函数被调用时，它的变量的空间是创建于运行的堆栈上的。以前调用的函数的变量仍保留在堆栈上，但它们被新函数的变量所掩盖，因此是不能访问的。

当递归函数调用自身时，情况也是如此。每进行一次新的调用，都将创建一批变量，它们掩盖递归函数前一次调用所创建的变量。当我们追踪一个递归函数的执行过程时，必须把分属不同次调用的变量区分开来，避免混淆。

我们上面写的函数中有两个变量：参数value和局部变量quotient。下面的一些图显示了堆栈的状态，当前可以访问的变量位于栈顶。所有其他调用的变量饰以灰色阴影，表示它们不能被当前正在执行的函数访问。

假定我们以4267这个值调用递归函数。当函数开始执行时，堆栈的内容如下图所示。


执行除法运算后，堆栈的内容如下：


接着，if语句判断出quotient的值非零，所以对该函数进行递归调用。当这个函数第二次被调用之初，堆栈的内容如下：


堆栈上创建了一批新的变量，隐藏了前面的那些变量，除非当前这次递归调用返回，否则它们是不能被访问的。再次执行除法运算之后堆栈的内容如下：


quotient的值现在为42，仍然非零，所以需要继续执行递归调用，并再创建一批变量。在执行完这次调用的除法运算之后，堆栈的内容如下：


此时，quotient的值还是非零，仍然需要执行递归调用。在执行除法运算之后，堆栈的内容如下：


不算递归调用语句本身，到目前为止所执行的语句只是除法运算以及对quotient的值进行测试。由于递归调用使这些语句重复执行，所以它的效果类似循环：当quotient的值非零实时，把它的值作为初始值重新开始循环。但是，递归调用将会保存一些信息（这点与循环不同），也就是保存在堆栈中的变量值。这些信息很快就会变得非常重要。

现在quotient的值变成了0，递归函数便不再调用自身，而是开始打印输出。然后函数返回，并开始销毁堆栈上的变量值。

每次调用putchar得到变量value的最后一个数字，方法是对value进行模10取余运算，其结果是一个0到9之间的整数。当它与字符常量'0'相加，其结果便是对应于这个数字的ASCII字符，然后把这个字符打印出来。


接着函数返回，它的变量从堆栈中销毁。接着，递归函数的前一次调用重新继续执行，它所使用的是自己的变量，它们现在位于堆栈的顶部。因为它的value值是42，所以调用putchar后打印出来的数字是2。


接着递归函数的这次调用也返回，它的变量也被销毁，此时位于堆栈顶部的是递归函数再前一次调用的变量。递归调用从这个位置继续执行，这次打印的数字是6。在这次调用返回之前，堆栈的内容如下：


现在我们已经展开了整个递归过程，并回到该函数最初的调用。这次调用打印出的数字7，也就是它的value参数除10的余数。


然后，整个递归函数就彻底返回到一开始调用它的地点。

如果你把打印出来的字符一个接一个排在一起，出现在打印机或屏幕上，你将看到正确的值：4267。

递归与迭代

递归是一种强有力的技巧，但也和其他技巧一样，它可能被误用。这里就有一个例子，如下图所示：


这个定义同时具备了我们开始讨论递归所需要的两个特性：存在限制条件，当符合这个条件时递归便不再继续：每次递归调用之后越来越接近这个限制条件。

用这种方式定义阶乘往往会引导人们使用递归来实现阶乘函数，如下程序：

    long fun(int n)

    {

      if (n <= 0)

        return 1;

      else

        return n * fun(n-1);

    }

这个函数能够产生正确的结果，但它并不是递归的良好用法。递归调用将涉及一些运行时开销------参数必须压倒堆栈中，为局部变量分配内存空间（所有递归均是如此，并非特指这个例子），寄存器的值必须保存等。当递归函数的每次调用返回时，上述这些操作必须还原，恢复成原来的样子。所以，基于这些开销，对于这个程序而言，它并没有简化问题的解决方案。

下面使用循环计算相同的结果：

    long fun(int n)

    {

      int result = -1;

      while(n > 1)

      {

        result *= n;

        n -= 1;

      }

      return result;

    }

尽管这个使用简单循环的程序不甚符合前面阶乘的数学定义，但它却能更为有效地计算出相同的结果。如果你仔细观察递归函数，你会发现递归调用是函数所执行的最后一项任务。这个函数是尾部递归（tail recursion）的一个例子。由于函数在递归调用返回之后不再执行任何任务，所以尾部递归可以很方便地转换成一个简单循环，完成相同的任务。