C++ 编写一个递归函数来反转输入字符串

Write a recursive function that reverses the input string

提问by Alex

I've been reading the book C++ For Everyone and one of the exercises said to write a function string reverse(string str)where the return value is the reverse of str.

我一直在阅读 C++ For Everyone 一书，其中一个练习说要编写一个string reverse(string str)返回值与str.

Can somebody write some basic code and explain it to me? I've been staring at this question since yesterday and can't figure it out. The furthest I've gotten is having the function return the first letter of str(Which I still don't know how it happened)

有人可以写一些基本的代码并向我解释吗？我从昨天开始就一直盯着这个问题，无法弄清楚。我得到的最远的是让函数返回的第一个字母str（我仍然不知道它是怎么发生的）

This is as far as I got (An hour after posting this question):

这是我得到的（发布这个问题一个小时后）：

string reverse(string str)
{
    string word = "";

    if (str.length() <= 1)
    {
        return str;
    }
    else
    {
        string str_copy = str;
        int n = str_copy.length() - 1;
        string last_letter = str_copy.substr(n, 1);

        str_copy = str_copy.substr(0, n);
        word += reverse(str_copy);
        return str_copy;
    }
    return word;
}

If I enter "Wolf", it returns Wol. Somebody help me out here If I return wordinstead of return str_copythen I get a wIf I return last_letterthen I get an l

如果我输入“Wolf”，它会返回 Wol。有人帮我在这里如果我return word而不是return str_copy然后我得到一个w如果我return last_letter那么我得到一个l

回答by David Harkness

I'll instead explain the recursive algorithm itself. Take the example "input" which should produce "tupni". You can reverse the string recursively by

相反，我将解释递归算法本身。以应该产生“tupni”的“输入”为例。您可以通过递归反转字符串

• If the string is empty or a single character, return it unchanged.
• Otherwise,
  1. Remove the first character.
  2. Reverse the remaining string.
  3. Add the first character above to the reversed string.
  4. Return the new string.

• 如果字符串为空或单个字符，则原样返回。
• 除此以外，
  1. 删除第一个字符。
  2. 反转剩余的字符串。
  3. 将上面的第一个字符添加到反转字符串中。
  4. 返回新字符串。

回答by Alois Kraus

Try this one

试试这个

string reverse(string &s)
{
    if( s.length() == 0 )  // end condtion to stop recursion
        return "";

    string last(1,s[s.length()-1]);  // create string with last character
    string reversed = reverse(s.substr(0,s.length()-1));
    return last+reversed; // Make he last character first
}

A recursive function must have the following properties

递归函数必须具有以下属性

• It must call itself again
• It must have a condition when the recursion ends. Otherwise you have a function which will cause a stack overflow.

• 它必须再次调用自己
• 当递归结束时，它必须有一个条件。否则你有一个函数会导致堆栈溢出。

This recursive function does basically create a string of the last character and then call itself again with the rest of the string excluding the last character. The real switching happens at the last line where last+reversed is returned. If it would be the other way around nothing would happen.

这个递归函数基本上创建了一个包含最后一个字符的字符串，然后用字符串的其余部分（不包括最后一个字符）再次调用自己。真正的切换发生在返回 last+reversed 的最后一行。如果情况相反，则什么都不会发生。

It is very inefficient but it works to show the concept.

这是非常低效的，但它可以展示这个概念。

回答by totjammykd

Just to suggest a better way of handling recursion:

只是建议一种更好的处理递归的方法：

String reversal using recursion in C++:

在 C++ 中使用递归进行字符串反转：

#include <iostream>
#include <string>
using namespace std;

string reverseStringRecursively(string str){
    if (str.length() == 1) {
        return str;
    }else{
        return reverseStringRecursively(str.substr(1,str.length())) + str.at(0);
    }
}

int main()
{
    string str;
    cout<<"Enter the string to reverse : ";
    cin>>str;

    cout<<"The reversed string is : "<<reverseStringRecursively(str);
    return 0;
}

回答by sbi

I won't write a full-blown algorithm for you, but here's a hint:

我不会为你写一个完整的算法，但这里有一个提示：

How about swapping the two outermost characters, and then apply the same to the characters in the middle?

如何交换最外面的两个字符，然后将相同的应用于中间的字符？

Oh, and if that book really proposed string reverse(string str)as an appropriate function signature for this, throw it away and buy a good bookinstead.

哦，如果那本书真的建议string reverse(string str)作为一个合适的函数签名，把它扔掉，买一本好书。

回答by Ann Orlova

Here is my version of a recursive function that reverses the input string:

这是我的递归函数版本，用于反转输入字符串：

void reverse(char *s, size_t len)
{
    if ( len <= 1 || !s )
    {
        return;
    }
    std::swap(s[0], s[len-1]);// swap first and last simbols
    s++; // move pointer to the following char
    reverse(s, len-2); // shorten len of string
}

回答by Prem K Chettri

Shortest and easiest

最短和最简单

class Solution {
public:
    string reverseString(string s) {
        string str;
        if(s != "
#include <iostream>
#include <string>

std::string
r(std::string s)
{
    if (s.empty())
        return s;
    return r(s.substr(1)) + s[0];
}

int
main()
{
    std::cout << r("testing") << std::endl;
}
"){
            str = reverseString(s.substr(1, s.length()));
            str += s.substr(0,1);
        }
        return str;    
    }   
};

回答by cnst

All existing solutions had way too much code that didn't really do anything, so, here's my take at it:

所有现有的解决方案都有太多的代码没有真正做任何事情，所以，这是我的看法：

template <typename BidirIt>
void reverse(BidirIt first, BidirIt last)
{
    if((first == last) || (first == --last))
        return;

    std::iter_swap(first, last);
    reverse(++first, last);
}

---

---

P.S. I stumbled upon this question trying to find a C++ way for std::stringof what s+1for a char *in C is; without going the whole route of s.substr(1, s.length()-1), which looks too ugly. Turns out, there's std::string::npos, which means until the end of the string, and it's already the default value for the second argument, so, s.substr(1)is enough (plus, it also looksmore efficient and on par with the simple s + 1in C).

PS我偶然发现了这个问题，试图找到一个C ++的方式对std::string什么s+1的char *在C是; 不走整个路线s.substr(1, s.length()-1)，看起来太丑了。事实证明，有std::string::npos，这意味着直到字符串的末尾，而且它已经是第二个参数的默认值，所以，s.substr(1)就足够了（另外，它看起来也更高效，与s + 1C 中的 simple 相当）。

---

---

Note, however, that recursion in general doesn't scale as the input grows larger, unless the compiler is able to do what is known as tail-recursion optimisation. (Recursion is rarely relied upon in imperative languages.)

但是请注意，递归一般不会随着输入变大而扩展，除非编译器能够执行所谓的尾递归优化。（命令式语言很少依赖递归。）

However, in order for the tail recursion optimisation to get activated, it is generally required that, (0), the recursion only happens within the returnstatement, and that, (1), no further operations are performed with the result of the recursive call back in the parent function.

但是，为了使尾递归优化被激活，一般要求，（0），递归只发生在return语句内，并且，（1），递归调用的结果不进行进一步的操作回到父函数。

E.g., in the case above, the + s[0]is logically done by the parent after the child call completes (and it probably would be so even if you go the more uglier s[s.length()-1] +route), so, it might as well prevent most compilers from doing a tail-recursion-optimisation, thus making the function very inefficient on large inputs (if not outright broken due to heap exhaustion).

例如，在上面的情况下，在+ s[0]子调用完成后，父级在逻辑上完成了（即使你走更丑陋的s[s.length()-1] +路线，也可能是这样），所以，它也可能阻止大多数编译器做一个尾巴 -递归优化，从而使函数在大输入上非常低效（如果不是由于堆耗尽而彻底损坏）。

(For what it's worth, I've tried writing a more tail-recursion-friendly solution (making sure to grow the return result through an argument to the function itself), but disassembly of the resulting binary seems to suggest that it's more involved than that in the imperative languages like C++, see gcc: is there no tail recursion if I return std::string in C++?.)

（对于它的价值，我已经尝试编写一个对尾递归更友好的解决方案（确保通过函数本身的参数来增加返回结果），但是对生成的二进制文件的反汇编似乎表明它比在像 C++ 这样的命令式语言中，请参阅gcc：如果我在 C++ 中返回 std::string，是否没有尾递归？。）

回答by MORTAL

you can implement your own reverse similar to std::reverse.

您可以实现自己的类似于 std::reverse 的反向。

ReverseString(str,0,str.length()-1);

回答by Marco167

I did something like this, it did the reversal in place. I took two variables that traverse the string from two extreme end to the centre of the string and when they overlap or equal to each other then reversal terminates.

我做了这样的事情，它在原地进行了逆转。我取了两个变量，它们从字符串的两端到字符串的中心遍历字符串，当它们相互重叠或相等时，反转终止。

Take an example: input string str = "abcd"and call the function as

举个例子：输入string str = "abcd"并调用函数

string ReverseString(string& str,int i,int j){
        if(str.length() < 1 || str == "" || i >= j){
            return "";
        }

        else{
            char temp = str[i];
            str[i] = str[j];
            str[j] = temp;
            ReverseString(str,i+1,j-1);
        }
        return str;
    }

and increment/decrement the variable pointers recursively. First the pointers points to 'a'and 'd'and swap them, then they point to 'b'and 'c'and swap them. Eventually i >= jwhich calls for the base case to be true and hence the recursion terminates. The main take away for this question is to pass input string as reference.

并递归地递增/递减变量指针。首先指针指向'a'，并'd'和交换他们，然后他们指向'b'并'c'和交换他们。最终i >= j要求基本情况为真，因此递归终止。这个问题的主要内容是将输入字符串作为参考传递。

void c_plusplus_recursive_swap_reverse(std::string::iterator start, 
    std::string::iterator end) 
{
    if(start >= end) {
        return;
    }

    std::iter_swap(start, end);
    c_plusplus_recursive_swap_reverse(++start, --end);
}

回答by ArmenB

I know I shouldn't give a solution, but since no one mentioned this easy solution I though I should share it. I think the code literally is the algorithm so there is no need for a pseudo-code.

我知道我不应该给出解决方案，但既然没有人提到这个简单的解决方案，我想我应该分享它。我认为代码字面上就是算法，所以不需要伪代码。

c_plusplus_recursive_swap_reverse(temp.begin(), temp.end());

To call it use:

调用它使用：

##代码##