递归

如果一个函数调用了自身，那么我们就说这里发生了递归。下面是一个写得不好的递归函数示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <iostream>

void countDown(int count)
{
    std::cout << "push " << count << '\n';
    countDown(count-1); // countDown() 递归地调用自身
}

int main()
{
    countDown(5);

    return 0;
}

当调用countDown(5)时，它会打印“push 5”，并调用countDown(4)。countDown(4)打印“push 4”并调用countDown(3)。countDown(3)打印“push 3”并调用countDown(2)。countDown(n)调用countDown(n-1)的序列会无限重复，形成无限递归调用。

在上一节课中，我们了解到每个函数调用都会导致函数相关数据被放到调用栈上。由于countDown()函数从不返回（它只是再次调用countDown()），因此这些信息永远不会从栈中弹出！因此，在某个时刻，计算机会耗尽栈内存，导致栈溢出，程序将崩溃或终止。在作者的机器上，该程序在终止之前倒数到了-11732！

递归终止条件

递归函数调用通常像普通函数调用一样工作。然而，上面的程序说明了递归函数最重要的区别：必须包含递归终止条件，否则它们将“永远”运行（实际上，是直到调用栈耗尽内存）。递归终止条件是一种判断条件，当满足该条件时，会让递归函数停止调用自身。

递归终止通常涉及使用if语句。下面是使用终止条件（和一些额外的输出）重新设计的函数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <iostream>

void countDown(int count)
{
    std::cout << "push " << count << '\n';

    if (count > 1) // 终止判断
        countDown(count-1);

    std::cout << "pop " << count << '\n';
}

int main()
{
    countDown(5);
    return 0;
}

现在，当我们运行程序时，countDown()将首先输出以下内容：

1
2
3
4
5

push 5
push 4
push 3
push 2
push 1

如果此时查看调用栈，您将看到以下内容：

1
2
3
4
5
6

countDown(1)
countDown(2)
countDown(3)
countDown(4)
countDown(5)
main()

由于终止条件，countDown(1)不会调用countDown(0)——相反，“if语句”不执行，因此它打印“pop 1”，然后终止。此时，countDown(1)从栈中弹出，函数返回到countDown(2)。countDown(2)会在调用countDown(1)结束后的位置恢复执行，因此它打印“pop 2”，然后终止。递归函数调用随后陆续从栈中弹出，直到countDown的所有实例都被弹出。

因此，该程序整体的输出是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

push 5
push 4
push 3
push 2
push 1
pop 1
pop 2
pop 3
pop 4
pop 5

值得注意的是，“push”输出按正向顺序发生，因为它们出现在递归函数调用之前。“pop”输出则以相反顺序出现，因为它们发生在递归函数调用之后，此时函数正在从栈中弹出（这与它们被放入栈中的顺序相反）。

一个更有用的例子

我们已经讨论了递归函数调用的基本机制，现在来看另一个稍微更典型的递归函数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// 计算 1 到 sumto 之和
// 如果是负数，返回 0
int sumTo(int sumto)
{
    if (sumto <= 0)
        return 0; // 判断非预期的输入 (终止条件)
    if (sumto == 1)
        return 1; // 正常输入时的基础情形 (终止条件)

    return sumTo(sumto - 1) + sumto; // 递归调用
}

让我们看看当用参数sumto=5调用这个函数时会发生什么。

1
2
3
4
5

sumTo(5) 被调用, 5 <= 1 是 false, return sumTo(4) + 5.
sumTo(4) 被调用, 4 <= 1 是 false, return sumTo(3) + 4.
sumTo(3) 被调用, 3 <= 1 是 false, return sumTo(2) + 3.
sumTo(2) 被调用, 2 <= 1 是 false, return sumTo(1) + 2.
sumTo(1) 被调用, 1 <= 1 是 true,  return 1.  遇到终止条件

现在，回退调用栈（在每个函数返回时将其从调用栈中弹出）：

1
2
3
4
5

sumTo(1) returns 1.
sumTo(2) returns sumTo(1) + 2, 结果 1 + 2 = 3.
sumTo(3) returns sumTo(2) + 3, 结果 3 + 3 = 6.
sumTo(4) returns sumTo(3) + 4, 结果 6 + 4 = 10.
sumTo(5) returns sumTo(4) + 5, 结果 10 + 5 = 15.

这样，就比较容易看出我们正在把1到传入值之间的数字相加。

因为递归函数比较难通过阅读代码来理解，所以好的注释特别重要。

注意，在上面的代码中，我们使用sumto-1而不是–sumto进行递归。这样做是因为操作符–有副作用，并且在同一表达式中多次使用带有副作用的变量可能导致未定义的行为。使用sumto-1可以避免副作用，使sumto在表达式中多次使用时仍然安全。

递归算法

递归函数通常先递归地找到问题的子集，然后通过解决子集问题来聚合得到最终结果。在上面的算法中，sumTo(value)首先求解sumTo(value-1)，然后将结果与value的值相加，以得到sumTo(value)的解。

在许多递归算法中，一些输入会直接产生普通输出。例如，sumTo(1)直接输出1，并且不需要进一步递归。这种可以直接得到输出的场景称为基本情况。基本情况充当算法的终止条件。通常可以通过考虑输入0、1、““或null时的输出来识别基本情况。

斐波那契数

最著名的数学递归算法之一是斐波那契数列。斐波那契数列出现在自然界的许多地方，例如树木的分枝、贝壳的螺旋、菠萝的小果、未卷曲的蕨类叶子以及松果的排列。

斐波那契数在数学上定义为：

1
2
3
4

f(n) =	0 if n = 0
        1 if n = 1
        f(n-1) + f(n-2) if n > 1

因此，编写一个（不是非常有效的）递归函数来计算第n个斐波那契数是相当简单的：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <iostream>

int fibonacci(int count)
{
    if (count == 0)
        return 0; // 基本情况
    if (count == 1)
        return 1; // 基本情况
    return fibonacci(count-1) + fibonacci(count-2);
}

// 计算和展示前13个斐波那契数列
int main()
{
    for (int count { 0 }; count < 13; ++count)
        std::cout << fibonacci(count) << ' ';

    return 0;
}

运行程序会产生以下结果：

1

0 1 1 2 3 5 8 13 21 34 55 89 144

记忆化算法

上面的递归Fibonacci算法并不高效，部分原因是每次调用Fibonacci的非基本情况都会导致两次以上的Fibonacci调用。这会产生指数数量的函数调用（事实上，上面的示例调用fibonacci()共1205次！）。可以使用一些技术来减少所需的调用数量，例如缓存开销较大的函数调用结果，以便在相同输入再次出现时直接返回结果。

下面是递归斐波那契算法的记忆化版本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <iostream>
#include <vector>

// count 这里是 std::size_t，以便更容易访问 std::vector
int fibonacci(std::size_t count)
{
	// 使用 std::vector 缓存计算结果
	static std::vector results{ 0, 1 };

	// 如果算过，那么直接返回结果
	if (count < std::size(results))
		return results[count];

	// 否则进行计算
	results.push_back(fibonacci(count - 1) + fibonacci(count - 2));
	return results[count];   
}

// 计算和展示前13个斐波那契数列
int main()
{
	for (int count { 0 }; count < 13; ++count)
		std::cout << fibonacci(static_cast<std::size_t>(count)) << ' ';

	return 0;
}

这个记忆化版本进行了35次函数调用，比原始算法的1205次要好得多。

递归与迭代

关于递归函数，经常被问到的一个问题是：“如果可以用迭代方式执行许多相同任务（使用for循环或while循环），为什么还要使用递归函数？”事实证明，递归问题总是可以用迭代方式解决——然而，对于稍微复杂的问题，递归版本通常更易于编写（和阅读）。例如，虽然可以用迭代方式编写斐波那契函数，但这要稍微困难一些！（试试看！）

迭代函数（那些使用for循环或while循环的函数）几乎总是比对应的递归函数执行效率更高。这是因为每次调用函数时，推送和弹出栈帧都会产生一定开销。迭代函数避免了这种开销。

这并不是说迭代函数总是更好的选择。有时，函数的递归实现非常清晰，也很容易编写，因此为了可维护性，承担一点额外开销是值得的，特别是在算法不需要递归太多次就能找到解决方案时。

通常，当满足以下大多数条件时，递归是一个不错的选择：

1. 递归代码的实现要简单得多。
2. 递归深度可以是有限的。
3. 该算法的迭代版本需要管理数据栈。
4. 这不是代码的性能关键部分。

如果递归算法更易于实现，可以先以递归方式实现，之后有需要时再优化为迭代算法。

习题

问题 1

整数N的阶乘（写作N!）定义为1到N之间所有数字的乘积（0! = 1）。编写一个名为factorial的递归函数，返回输入的阶乘。用前7个阶乘测试它。

提示：记住(x * y) = (y * x)，因此1到N之间所有数字的乘积，与N到1之间所有数字的乘积是相同的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <iostream>

int factorial(int n)
{
	if (n <= 0)
		return 1;

	return factorial(n - 1) * n;
}

int main()
{
	for (int count { 0 }; count < 7; ++count)
		std::cout << factorial(count) << '\n';
}

问题 2

编写一个递归函数，接受一个整数作为输入，并返回该整数各位数字之和（例如357 = 3 + 5 + 7 = 15）。对输入93427打印结果（结果为25）。假设输入值都是正数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <iostream>

int sumDigits(int x)
{
	if (x < 10)
		return x;

	return sumDigits(x / 10) + x % 10;
}

int main()
{
	std::cout << sumDigits(93427);
}

问题 3

3a) 这道题稍微麻烦一些。编写一个程序，要求用户输入一个正整数，然后用一个递归函数打印该数字的二进制表示。请使用「附录O.4 二进制与十进制表示之间的转换」中的方法1。

提示：使用方法1时，我们希望按相反的顺序打印各个二进制位。这意味着打印语句应当放在递归调用之后。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>

// 感谢读者 Gapo 提供的这个解法
void printBinary(int x)
{
        // 终止条件
	if (x == 0)
		return;

	// 递归处理下一位
	printBinary(x / 2);

	// 打印各次余数（顺序相反）
	std::cout << x % 2;
}

int main()
{
	int x;
	std::cout << "Enter a positive integer: ";
	std::cin >> x;

	printBinary(x);
}

3b) 附加题：修改3a的代码，使其能够处理用户输入0或负数的情形。

下面是输出示例（假设int为32位）：

Enter an integer: -15
11111111111111111111111111110001

提示：你的printBinary()函数其实不需要处理负数。只要传给它一个与负数具有相同二进制表示的正数，就能得到正确的输出。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// 感谢读者 Donlod 提供的这个解法
#include <iostream>

void printBinary(unsigned int n)
{
	if (n > 1) // 只有 n > 1 时才递归，因此这里是 n == 0 的终止条件
	{
		printBinary(n / 2);
	}

	std::cout << n % 2;
}

int main()
{
	int x{};
	std::cout << "Enter an integer: ";
	std::cin >> x;

	printBinary(static_cast<unsigned int>(x));
}