什么是递归函数

前面的学习过程中，我们已经看到过很多调用其他函数的函数实例。例如，函数 A 可以调用函数 B，而函数 B 又可以调用函数 C。

实际上，函数也可以调用它自己。调用自己的函数称为递归函数。来看以下 message 函数：

void message()
{
    cout << "This is a recursive function. /n";
    message();
}

该函数显示字符串 "This is a recursive function."，然后调用它自己。每次它调用自己时，循环都会重复。现在应该能发现该函数的问题，因为它没有办法停止递归调用。这个函数就像一个无限循环，因为没有代码阻止它重复。

要使递归函数有用，则递归函数必须有一个方法来控制递归调用的次数。以下是对 message 函数的修改。它传递了一个整数参数，该参数将保存函数调用自己的次数。

void message(int times)
{
    if (times > 0)
    {
        cout << "This is a recursive function./n";
        message(times - 1);
    }
}

该函数包含一个控制递归的 if 语句。只要 times 参数大于零，它将显示消息并再次调用自己。每次它调用自己时，都会传递 times-1 作为参数。例如，假设有一个程序使用以下语句来调用该函数：

message(3);

参数 3 将导致函数被调用 4 次。第一次调用函数时，if 语句将显示消息并以 2 作为参数调用自身，如图 1 所示。

图 1 直观地说明了两次独立的 message 函数调用。每次调用该函数时，会在内存中创建一个 times 参数的新实例。函数第一次被调用时，times 参数被设置为 3；当函数调用自己时，会创建一个新的 times 实例，并将值 2 传递给它。如此循环往复，直到传递给函数的值变成了  0，如图 2 所示。

从图 2 可以看到，该函数将被调用 4 次，所以递归的深度是 4。当函数到达第 4 次调用时，times 参数将被设置为 0。此时，if 语句将停止调用的递归链，并且将返回函数的第 4 个实例。程序的控制权将从函数的第 4 个实例返回到第 3 个实例中调用递归函数语句所在的位置：

if (times > 0)
{
    cout << "This is a recursive function./n";
    message(times - 1);
}

因为在函数调用之后没有更多的语句要执行，所以函数的第 3 个实例会将程序的控制权返回给第 2 个实例。如此重复，直到函数的所有实例都返回。

下面的程序演示了修改后的递归 message 函数，它可以显示每次调用时参数的值。

// This program demonstrates a simple recursive function.
#include <iostream>
using namespace std;

//Function prototype
void message(int);

int main()
{
    message(3);
    return 0;
}
void message(int times)
{
    if (times > 0)
    {
        cout << "Message " << times << "/n";
        message(times - 1);
    }
}

程序输出结果：

Message 3
Message 2
Message 1

递归函数可以通过将复杂的问题分解成相同类型的子问题。这个分解过程在到达一个基本情况时就停止了，也就是说，一个简单的子问题足以被直接解决。例如，在前面示例的递归 message 函数中，基本情况是当参数 times 等于 0 时。

为了进一步说明这个递归函数的内部工作，不妨来看一看另一个版本的程序。下面的程序中，每次进入函数都会显示一条消息，并且在函数返回之前显示另一条消息。

// This program demonstrates a simple recursive function.
#include <iostream>
using namespace std;

// Function prototype
void message(int);

int main()
{
    message(3);
    return 0;
}
void message(int times)
{
    cout << "Message " << times << "./n";
    if (times > 0)
    {
        message(times - 1);
    }
    cout << "Message " << times << " is returning./n";
}

程序输出结果：

Message 3.
Message 2.
Message 1.
Message 0.
Message 0 is returning.
Message 1 is returning.
Message 2 is returning.
Message 3 is returning.

当有一种方法可以将要解决的问题从某个方面分化为更简单或更小的、相同类型的问题时，即可考虑使用递归。

例如，如果有一长串的名称列表需要排序，则可以将列表分成两个子列表，并将两个子列表分配给两个不词的人来排序。一旦子列表完成排序，它们可以通过合适的整理过程合并形成原始列表的排序版本中。

在这种情况下，排序子列表的问题就是相同类型的更简单的问题。子列表实际上还可以再拆分，而基本情况就出现在子列表中只有一个名称时。

现在来看一个执行实用任务的简单递归示例。函数 frequency 可以计算特定字符出现在字符串中的次数。

int frequency(char ch, string inputString, int position)
{
    if (position == inputString. length () ) //基本情况
        return 0;
    if (inputString[position] == ch)
        return 1 + frequency(ch, inputString, position+1);
    else
        return frequency(ch, inputString, position+1);
}

该函数的参数包括：

• ch：要搜索和计数的字符。
• inputString：要搜索的字符串。
• position：搜索的起始下标。

第一个 if 语句确定是否已出现基本情况，即到达字符串的结尾：

if (position == inputString.length())
    return 0;

如果已经到达字符串的末尾，则函数返回 0，表示没有更多的字符要计数。否则，执行以下 if 语句：

if (inputString[position] == ch)
    return 1 + frequency(ch, inputString, position+1);
else
    return frequency(ch, inputString, position+1);

如果 inputString [position] 是搜索字符，则函数执行递归调用。返回语句返回 1 加上搜索字符在字符串中出现的次数，从 position+1 开始。如果 inputString [position] 不是搜索字符，则会进行递归调用以搜索字符串的其余部分。下面的程序演示了以上示例。

// This program demonstrates a recursive function for
// counting the number of times a character appears
// in a string.
#include <iostream>
#include <string>
using namespace std;
// Function prototype

int frequency(char ch, string inputString , int pos);
int main()
{
    string inputString = "abcddddef";
    cout << "The letter d appears " << frequency ('d', inputString, 0) << " times./n";
    return 0;
}
int frequency(char ch, string inputString, int position)
{
    if (position == inputString.length()) //base case
        return 0;
    if (inputString[position] == ch)
        return 1 + frequency(ch, inputString, position+1);
    else
        return frequency(ch, inputString, position+1);
}

程序输出结果：

The letter d appears 4 times.

直接递归和间接递归

迄今为止，我们所讨论的例子都是直接调用自己的递归函数，这称为直接递归。也可以在程序中创建间接递归。

例如，当函数 A 调用函数 B，而函数 B 又反过来调用函数 A 时，就会发生这种情况。在间接递归中甚至可能包含若干个函数。例如，函数 A 调用函数 B，函数 B 调用函数 C，而函数 C 又调用函数 A。