每周云分享

为了理解透这个知识点，我打算分几个角度讲述这一知识点，力争面面俱到，图文并茂。

首先，我们先理解一下递归的概念。

2、在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。 

3、递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

4、在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

好吧，一下子说这些概念也没意思，我们来讲解一下递归的过程吧。

具体地说，如果递归函数调用自己，则被调用的函数也将调用自己，这将无限循环下去，除非代码中包含终止调用链的内容。通常的方法将递归调用放在if语句中。例如，void类型的递归函数recurs()的代码如下：

void recurs(argumentlist){
    statements1
    if(test)　　　　　　//test最终为false，调用链将断开
        recurs(arguments)
    statements2
}
下面我们用文字再现这段代码块的内容。只要if语句为true，每个recurs()调用都将执行statement1，然后再调用recurs()，而不会执行statements2 。当前调用结束后，程序控制权将返回给调用它的recurs()，而该recurs()将执行其statements2部分，然后结束，并将控制权返回给前一个调用，依次类推。

光有文字说服力不够，我们来看一个类似此递归的过程图：

因此，如果recurs()进行了5次递归调用，则第一个statements1部分将按函数调用的顺序执行5次，然后statements2部分将以与函数调用相反的顺序执行5次。进入5层递归后，程序将沿进入的路径返回。下面这段程序演示了这种行为：

// recur.cpp -- using recursion
#include <iostream>
void countdown(int n);
int main()
{
    countdown(4);           // call the recursive function
    return 0;
}

void countdown(int n)
{
    using namespace std;
    cout << "Counting down ... " << n << endl;
    if (n > 0)
        countdown(n-1);     // function calls itself
    cout << n << ": Kaboom!\n";
}

该程序的输出如下：

Counting down ... 4　　　　< level 1；adding levels of recursion

Counting down ... 3　　　　< level 2

Counting down ... 2　　　　< level 3

Counting down ... 1　　　　< level 4

Counting down ... 0　　　　< level 5；final recursive call（调用）

0: Kaboom!　　　　　　　   < level 5；beginning to back out

1: Kaboom!　　　　　　　   < level 4

2: Kaboom!　　　　　　　   < level 3

3: Kaboom!　　　　　　　   < level 2

4: Kaboom!　　　　　　      < level 1

注意，每个递归调用都创建自己的一套变量，因此当程序到达第5次调用时，将有5个独立的n变量，其中每个变量的值都不同。

我们修改一下上段的程序来验证这一观点。

 View Code

 程序输出：

注意，在一个内存单元（内存地址为0x6cfed0），存储的n值为4；在另一个内存单元（内存地址为0012FD34），存储的n值为3；等等。另外，注意到Counting down阶段和Kaboom阶段的相同层级，n地址相同。

上面的程序中只有一个递归，而我们在创建二叉树或其他操作时往往用到两个递归，那么我们再介绍一下包含多个递归调用的递归。

在需要将一项工作不断分为两项较小的、类似的工作时，递归非常有用。例如，请考虑使用这种方法来绘制标尺的情况。标出两端，找到中点并将其标出。然后将同样的操作作用于标尺的左半部分和右半部分。如果要进一步细分，可将同样的操作用于当前的每一部分。递归方法有时被称为分而治之策略。

下面这段程序使用递归函数subdivide()演示了上面讲的方法，该函数使用一个字符串，该字符串除两端为 | 字符外，其他全部为空格。main函数使用循环调用subdivide()函数6次，每次将递归层编号加1，并打印得到的字符串。这样，每行输出表示一层递归。
// ruler.cpp -- using recursion to subdivide a ruler
#include <iostream><br>using namespace std;
const int Len = 66;
const int Divs = 6;
void subdivide(char ar[], int low, int high, int level);
int main()
{
    char ruler[Len];
    int i;
    for (i = 1; i < Len - 2; i++)
        ruler[i] = ' ';
    ruler[Len - 1] = '\0';
    int max = Len - 2;
    int min = 0;
    ruler[min] = ruler[max] = '|';
    cout << ruler << endl;
    for (i = 1; i <= Divs; i++){
        subdivide(ruler,min,max, i);
        cout << ruler << endl;
        for (int j = 1; j < Len - 2; j++)
            ruler[j] = ' ';             // reset to blank ruler
    }
    return 0;
}
 
void subdivide(char ar[], int low, int high, int level)
{
    if (level == 0)
        return;
    int mid = (high + low) / 2;
    ar[mid] = '|';
    subdivide(ar, low, mid, level - 1);
    subdivide(ar, mid, high, level - 1);
}

subdivide()函数使用变量level来控制递归层。函数调用自身时，将把level减1，当level为0时，该函数将不再调用自己。注意，subdivide()调用自己两次，一次针对左半部分，另一次针对右半部分。最初的中点被用作一次调用的右端点和另一次调用的左端点。请注意，调用次数将呈几何级数增长，也就是说，调用一次导致两个调用，然后导致4个调用，再导致8个调用，依次类推。这就是6层调用能够填充64个元素的原因（26=64）。这将不断导致函数调用数（以及存储的变量数）翻倍，因此如果要求的递归层次很多，这种递归方式将是一种糟糕的选择；然而，如果递归层次较少，这将是一种精致的而简单的选择。

程序输出：

上面具体讲解了递归的过程和实现细节，我们似乎有一种似懂非懂的feeling，这就对了，递归这么难理解的东西，休想这么快掌握。