2.3  执行动作的递归（2）

注释：writeBackward不返回计算值

另一个解决方案  现在看一个稍有些不同的问题解决方案。回想一下，从字符串中去掉字符有两种选择：去掉最后一个字符或去掉第一个字符。上述解决方案去掉字符串的最后一个字符。下面将根据第二种选择创建解决方案：

去掉第一个字符

开始时，考虑对前述伪代码解决方案的简单修改，用first替换last。这样，函数输出第一个字符，而不是最后一个，然后递归地逆置字符串的其余部分。
 

writeBackward1(s: string)  
if (the string s is empty)  
Do nothing —this is the base case  
else  
{  
Write the first character of s  
writeBackward1(s minus its first character)  
}  

此解决方案能达到预期效果吗？仔细分析可知，它按一般的从左至右方向输出字符串，而不是逆置。伪代码中的步骤为：

输出s的第一个字符

输出s的其余部分

这些步骤仅输出字符串s。虽将函数命名为writeBackward，但并没有真正逆置字符串--递归不是万能的。

可通过下列递归描述来正确地逆置s：

去掉第一个字符，然后逆置字符串s

输出字符串s的第一个字符

换句话说，先逆置s的其余部分，再输出s的第一个字符。这种方法的伪代码解决方案如下所示：
 

writeBackward2(s: string)  
if (the string s is empty)  
Do nothing —this is the base case  
else  
{  
writeBackward2(s minus its first character)  
Write the first character of s  
}  

writeBackward2转换得到的C++代码与原始writeBackward函数类似，我们将此留作练习。

在此有必要仔细跟踪上述两个伪代码函数writeBackward和writeBackward2的操作。首先在各个函数中添加语句，以提供有利于跟踪的输出。
 

writeBackward(s: string)  
cout << "Enter writeBackward with string: " << s << endl;  
if (the string is empty)  
Do nothing —this is the base case  
else  
{  
cout    << "About to write last character of string: "  
<< s << endl;  
Write the last character of s  
writeBackward(s minus its last character) // Point A  
}  
cout << "Leave writeBackward with string: " << s << endl;  
writeBackward2(s: string)  
cout    << "Enter writeBackward2 with string: "  
<< s << endl;  
if (the string is empty)  
Do nothing —this is the base case  
else  
{  
writeBackward2(s minus its first character) // Point A  
cout    << "About to write first character of string: "  
<< s << endl;  
Write the first character of s  
}  
cout << "Leave writeBackward2 with string: " << s << endl;