递归

递归是一种编程技术，允许程序员用自身来表示操作。在 C 语言中，这表现为一个调用自身的函数。理解递归函数的一个有用方法是想象一个正在执行的过程，其中一个指令是“重复该过程”。这听起来非常类似于循环，因为它重复相同的代码，并且在某些方面与循环相似。另一方面，递归使得表达那些需要递归调用的结果才能完成任务的思想变得更容易。当然，必须有可能在某些情况下“过程”在没有递归调用的情况下完成。一个简单的例子是建造一个十英尺高的墙；如果我想建造一个十英尺高的墙，那么我会先建造一个九英尺高的墙，然后再加上一英尺的砖块。从概念上讲，这就像说“建墙”函数接受一个高度，如果该高度大于一，首先调用自身来建造一个较低的墙，然后加上一英尺的砖块。

递归的一个简单例子是：

void recurse()
{
    recurse(); /* 函数调用自身 */
}
 
int main()
{
    recurse(); /* 触发递归 */
    return 0;
}

这个程序不会永远继续下去。计算机将函数调用保存在栈上，一旦调用次数过多而没有结束，程序就会崩溃。为什么不写一个程序来查看函数被调用多少次才会终止呢？

#include <stdio.h>
 
void recurse ( int count ) /* 每个调用都有自己的count副本 */
{
    printf( "%d\n", count );
    /* 没有必要增加count，因为每个函数的变量都是独立的（因此每个count将被初始化大一个）。
     */
    recurse ( count + 1 );
}
 
int main()
{
  recurse ( 1 ); /* 第一个函数调用，从1开始 */
  return 0;
}

这个简单的程序将通过初始化每个函数调用的计数变量为比之前多 1（通过传递 count + 1），来显示 recurse 函数被调用的次数。请注意，这不是函数调用自我重启；而是数百个未完成的函数调用。

理解递归的最佳方式是认为每个函数调用都是计算机正在执行的“进程”。如果我们把程序想象成由一组可以传递任务状态信息和执行任务指令的人来执行，那么每个递归函数调用就像每个人都在等待第一个人的结果，同时让下一个人按照相同的一组指令来处理任务的一部分。

在某个时刻，我们将没有足够的人来执行指令，就像我们之前的递归函数耗尽了栈空间一样。我们需要一种方法来避免这种情况！为了停止一系列递归调用，递归函数将有一个条件来控制函数何时最终停止调用自身。函数不会调用自身的条件称为函数的基本情况。基本上，它通常是一个 if 语句，检查某个变量是否满足某个条件（例如一个数字小于零，或者大于另一个数字），如果这个条件为真，它将不允许函数再次调用自身。（或者，它可以检查某个条件是否为真，并且只有在这种情况下才允许函数调用自身）。

一个快速示例：

void count_to_ten ( int count )
{
    /* we only keep counting if we have a value less than ten */
       if ( count < 10 )   
       {
           count_to_ten( count + 1 );
       }
}
int main()
{
  count_to_ten ( 0 ); 
}

这个程序在我们数到十时结束，或者更精确地说，当 count 不再小于十时结束。这是一个好的基本情况，因为它意味着如果我们有一个大于十的输入，我们会立即停止。如果我们选择在 count 等于十时停止，那么如果函数被输入 11 调用，它会在停止之前耗尽内存。

注意到到目前为止，我们还没有对递归函数调用的结果做任何处理。每次调用都会执行某些操作，但调用者会忽略这些操作。不过，确实有可能从调用者那里获取一个值。同时，也可以利用前一次调用的副作用。在任一情况下，一旦函数调用了自身，它就会准备好在调用后的下一行继续执行。它仍然可以执行操作。你可以编写一个函数来打印出数字123456789987654321。如何使用递归来编写一个完成这个任务的函数？只需让它持续增加传递进来的变量，然后输出这个变量两次：一次在函数递归之前，一次在递归之后。

#include <stdio.h>
void printnum ( int begin )
{
    printf( "%d", begin );
    if ( begin < 9 )         /* 基准情况是当begin不再小于9时 */
    {                        
        printnum ( begin + 1 ); 
    }
    /* 在我们已经打印完从1到9和从9到begin + 1的所有内容之后，再次显示begin */
    printf( "%d", begin );
}
 
int main()
{
    printnum(0);
    getchar();
}

这个函数之所以有效，是因为它会依次打印从 1 到 9 的数字，并且随着每个 printnum 函数的终止，它会继续在每个从 9 到 1 的函数中打印 begin 的值。

然而，这仅仅是触及了递归的实用性。这里有一个小挑战：使用递归来编写一个程序，该程序返回任何大于 0 的数的阶乘。（阶乘是：number * (number - 1) * (number - 2) ... * 1）。

提示：你的函数应该先递归地找到较小数字的阶乘，即它接收一个数字，找到前一个数字的阶乘，然后将这个数字乘以前一个数字的阶乘……祝你玩得开心。😃