编写一个反转输入字符串的递归函数

Question

我一直在阅读C++ For Everyone这本书,其中一个练习据说要编写一个string reverse(string str)返回值相反的函数str.

有人可以写一些基本代码并向我解释一下吗？从昨天开始我就一直盯着这个问题而无法理解.我得到的最远的是函数返回的第一个字母str(我还不知道它是怎么回事)

这是我得到的(发布此问题后一小时):

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;
}

如果我输入"狼",它将返回Wol.有人帮助我在这里如果我return word而不是return str_copy那时我得到一个w 如果我return last_letter然后我得到一个l

Answer 1

我有两分钟,所以我会解释递归算法本身.以"输入"为例,它应该产生"tupni".您可以通过递归方式反转字符串

• 如果字符串为空或单个字符,则保持不变.
• 除此以外,
  1. 删除第一个字符.
  2. 反转剩余的字符串.
  3. 将上面的第一个字符添加到反向字符串中.
  4. 返回新字符串.

Answer 2

试试这个吧

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
}

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

• 它必须再次召唤自己
• 递归结束时必须有一个条件否则你有一个函数会导致堆栈溢出.

这个递归函数基本上创建了最后一个字符的字符串,然后再次使用除最后一个字符之外的其余字符串调用自身.实际切换发生在返回last + reversed的最后一行.如果反过来会发生任何事情.这是非常低效的,但它可以显示这个概念.

你的,Alois Kraus

Answer 3

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

在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;
}