2.3 执行动作的递归（1）
递归函数不一定要返回值，可以是void函数。
递归void函数：逆置字符串
现考虑一个稍复杂的问题：给出一个由字符组成的字符串，将其逆序排列。例如，将字符串"cat"写为"tac"。要创建递归解决方案，需要回答2.1节末尾的提示中给出的4个问题。
可根据长度为n-1的字符串的逆置问题，来创建长度为n的字符串逆置问题的解决方案。换句话说，解决方案的各个递归步骤将要逆置的字符串的长度减1。字符串越来越短这个事实表明：一些非常短的字符串的问题可用作基例。最短的字符串是空字符串，其长度为0。可将问题的基例选择为：
逆置空字符串
注释：基例
基例的解决方案简单明了：什么都不用做(此外也可将长度为1的字符串用作基例)。
究竟如何用长度为n-1的字符串逆置问题的解决方案，来解决长度为n的字符串逆置问题呢？这与创建阶乘问题解决方案所用的方法类似，即用factorial(n-1)来计算factorial(n)。但又与阶乘问题不同，这个字符串问题并不存在一个直接明了的推进方法。很明显，并不是所有长度为n-1的字符串都能解决问题。例如，逆置"apple" (长度为5的字符串)与逆置"pear" (长度为4的字符串)之间没有关系。必须精心选择更小的问题，以将其解决方案用于原始问题的解决方案。
注释：如果可以将n-1个字符的字符串逆置，如何才能将n个字符的字符串逆置呢
所选的长度为n-1的字符串必须是原始字符串的一部分，即子串。假设从原始字符串去掉一个字符，留下长度为n-1的子串。为使递归解决方案有效，逆置子串的功能与其他辅助功能相组合，必须能够实现原始字符串的逆置。将这个方法与递归计算factorial的方法进行比较：计算factorial(n-1)的功能与将该值乘以n的功能组合，才具有计算factorial(n)的功能。
需要判断去掉的字符以及要执行的辅助任务。先考虑辅助任务。因为要输出字符，所以辅助任务是输出单个字符。至于要从字符串中去掉字符，则有几种可能的选择。两种直观选择如下：
去掉最后一个字符
或
去掉第一个字符
首先来看第一个选择，也就是去掉最后一个字符的情况，如图2-6所示。
要使该解决方案有效，必须先输出字符串中的最后一个字符。因此在逆置字符串的其余部分之前必须输出最后一个字符。对于给定的字符串s，高层递归解决方案如下：
- writeBackward(s: string)
- if (the string is empty)
- Do nothing —this is the base case
- else
- {
- Write the last character of s
- writeBackward(s minus its last character)
- }
注释：writeBackward将字符串逆置
提示：递归解决方案必然涉及一个或者多个较小的问题，这些问题比原始问题更加靠近基例。必须保证这些较小的问题最终能够到达基例，如果无法保证会导致无法终止的算法。
这是该问题的概念化解决方案。要获得C++函数，必须解决一些实现问题。假定函数要接收一个参数：要逆置的字符串s。所有字符(包括空格)都是这个字符串的一部分。C++函数writeBackward如下所示：
- /** Writes a character string backward.
- @pre The string s to write backward.
- @post None.
- @param s The string to write backward. */
- void writeBackward(string s)
- {
- int length = s.size(); // Length of string
- if (length > 0)
- {
- // Write the last character
- cout << s.substr(length-1, 1);
- // Write the rest of the string backward
- writeBackward(s.substr(0, length – 1)); // Point A
- } // end if
- // length == 0 is the base case - do nothing
- } // end writeBackward
注意，对writeBackward的递归调用使用了字符串s逐步变短的版本，以确保可到达基例。由于这个函数到达基例后什么都不做，因此并没有显式地处理基例。基例是隐式处理的。
可通过箱式跟踪来跟踪writeBackward的执行。与函数fact一样，各个箱包含递归调用的局部环境，本例中为输入参数s和局部变量length。此处的跟踪与图2-5所示的fact跟踪有些不同，因为作为void函数，writeBackward没有使用return语句返回计算结果。图2-7跟踪了使用字符串"cat"对writeBackward函数的调用。