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

| 我一直在阅读《面向所有人的C ++》一书，其中一项练习是写一个函数string reverse(string str)，其中返回值是value1ѭ的反面。有人可以写一些基本代码并向我解释吗？从昨天开始，我一直在盯着这个问题，无法解决。我得到的最远的结果是让函数返回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;
}

如果输入\“ Wolf \”，它将返回Wol。有人在这里帮我如果我是return word而不是return str_copy，那么我会得到w 如果我return last_letter，我得到an8ѭ

已邀请:

18 个回复

冲汉

相反，我将解释递归算法本身。以示例“ input”为例，该示例应产生“ tupni”。您可以通过以下方式递归反转字符串如果字符串为空或单个字符，则将其保持不变。除此以外，删除第一个字符。反转剩余的字符串。将上面的第一个字符添加到反向字符串中。返回新字符串。

超可林

试试这个

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的最后一行。如果这是另一种方法，那么什么也不会发生。它的效率很低，但是可以显示这个概念。

凡夕

只是为了建议一种更好的递归处理方法：在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;
}

凄挡

我不会为您编写完善的算法，但这是一个提示：交换两个最外面的字符，然后将其应用于中间的字符又如何呢？哦，如果那本书真的提出了“ 0”作为对此的适当功能签名，那就把它扔掉，然后买一本好书。

犀耽澄协吻

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

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
}

纫合峭

最短最容易

class Solution {
public:
    string reverseString(string s) {
        string str;
        if(s != \"\\0\"){
            str = reverseString(s.substr(1, s.length()));
            str += s.substr(0,1);
        }
        return str;    
    }   
};

究补闯

1行递归解决方案：

string RecursiveReverse(string str, string prev = \"\") {
    return (str.length() == 0 ? prev : RecursiveReverse(str.substr(0, str.length()-1), prev += str[str.length()-1]));
}

您这样称呼它：

cout << RecursiveReverse(\"String to Reverse\");

辅奈

我知道我不应该提供解决方案，但是由于没有人提到这个简单的解决方案，尽管我应该分享它。我认为代码实际上是算法，因此不需要伪代码。

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

要调用它，请使用：

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

视蕉梁拌客

所有现有的解决方案都有太多的代码，它们实际上并没有执行任何操作，因此，这是我的看法：

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

附言我偶然发现了这个问题，试图为C中的ѭ21中的s+1中的std::string找到一种C ++方式。却没有走22英镑的整个路线，看上去太难看了。原来，这里有ѭ23means，这意味着直到字符串结尾，并且它已经是第二个参数的默认值，因此s.substr(1)就足够了（此外，它看起来也更有效，并且与C中的简单s + 1）。但是请注意，递归通常不会随着输入的增长而扩展，除非编译器能够执行所谓的尾递归优化。（在命令式语言中很少依赖递归。）但是，为了激活尾部递归优化，通常要求（0），该递归仅在return语句内发生，并且（1），对递归的结果不执行进一步的操作在父函数中回调。例如，在上述情况下，+ s[0]是在子调用完成后由父级逻辑上完成的（即使您走的是更难看的s[s.length()-1] +路线也可能如此），因此，它也可能会阻止大多数编译器执行尾递归优化，从而使该函数在大输入时效率非常低（如果不是由于堆耗尽而彻底中断）。（为此，我尝试编写一种更加尾部递归友好的解决方案（确保通过函数本身的参数来增加返回结果），但是反汇编生成的二进制文件似乎表明它比像C ++这样的命令性语言所涉及的更多，请参阅gcc：如果我在C ++中返回std :: string，是否没有尾递归？）。

届甸衬丝蚕

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

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

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

先对冈蒲

我做了这样的事情，它做了适当的逆转。我使用了两个变量，它们从两个末端到字符串的中心遍历字符串，当它们重叠或彼此相等时，反转终止。举个例子：输入string str = \"abcd\"并将函数调用为

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

然后递归地递增/递减变量指针。首先，指针指向\'a\'和\'d\'并交换它们，然后它们指向\'b\'和\'c\'并交换它们。最终“ 36”要求基本情况成立，因此递归终止。这个问题的主要收获是传递输入字符串作为参考。

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

死狸蔽垂藐

字符串可以就地反转。如果从最小的字符串（即一个字符串）开始，则无需执行任何操作。这是我们停止或从递归调用返回的地方，它成为我们的基本情况。接下来，我们必须考虑一种交换最小字符串（即两个或更多字符）的通用方法。最简单的逻辑是将当前字符str[current_index]与另一侧的字符str[str_length-1 - current_index]交换。最后，再次调用反向函数以获取下一个索引。

#include <iostream>
using namespace std;

void reverse_string(std::string& str, int index, int length) {
  // Base case: if its a single element, no need to swap
  // stop swapping as soon as we reach the mid, hence index*2
  // otherwise we will reverse the already reversed string
  if( (length - index*2) <= 1 ) { 
    return;
  }

  // Reverse logic and recursion:

  // swap current and opposite index
  std::swap(str[index], str[length-1 - index]); 

  // do the same for next character (index+1)
  reverse_string(str, index+1, length);
}

int main() {
  std::string s = \"World\";
  reverse_string(s, 0, s.length());
  std::cout << s << endl;
}

谷起

已经有一些不错的答案，但是我想添加具有完整工作递归反转字符串的方法。

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

char * reverse_s(char *, char*, int,int);

int main(int argc, char** argv) {
if(argc != 2) {
        cout << \"\\n ERROR! Input String\";
        cout << \"\\n\\t \" << argv[0] << \"STRING\" << endl;
        return 1;
}       
        char* str = new char[strlen(argv[1])+1];
        strcpy(str,argv[1]);    
        char* rev_str = new char[strlen(str)+1];        
        cout<<\"\\n\\nFinal Reverse of \'\" << str << \"\' is --> \"<< reverse_s(str, rev_str, 0, strlen(str)) << endl;
        cin.ignore();
        delete rev_str, str;
        return 0;
}

char* reverse_s(char* str, char* rev_str, int str_index, int rev_index ) {
if(strlen(str) == 1)
        return str;

if(str[str_index] == \'\\0\' ) {
        rev_str[str_index] = \'\\0\';
        return rev_str;
}

str_index += 1;
rev_index -=1;

rev_str = reverse_s(str, rev_str, str_index, rev_index);
if(rev_index >= 0) {
        cout << \"\\n Now the str value is \" << str[str_index-1] << \" -- Index \" << str_in
dex << \" Rev Index: \" << rev_index;
        rev_str[rev_index] = str[str_index-1];

        cout << \"\\nReversed Value: \" << rev_str << endl;
}
return rev_str;
}

淘圃跺枯替

void reverse(string &s, int &m) {
    if (m == s.size()-1)
        return;
    int going_to = s.size() - 1 - m;
    string leader = s.substr(1,going_to);
    string rest = s.substr(going_to+1,s.size());
    s = leader + s.substr(0,1) + rest;
    reverse(s,++m);    
}
int main ()
{
  string y = \"oprah\";
  int sz = 0;
  reverse(y,sz);
  cout << y << endl;
  return 0;
}

捅瓶啡

void ClassName::strgRevese(char *str)
{
        if (*str==\'\\0\')
                return;
        else
                strgRevese(str+1);
        cout <<*str;
}

妊辽剁茧

这是我的三行字符串反转

std::string stringRevers(std::string s)
{
    if(s.length()<=1)return s;
    string word=s.at(s.length()-1)+stringRevers(s.substr(0,s.length()-1));//copy the last one at the beginning  and do the same with the rest
    return word;

}

芳菱挨啡

问题是要编写一个递归函数。这是一种方法。这不是一个整洁的代码，但是需要执行什么操作。

/* string reversal through recursion */
#include <stdio.h>
#include <string.h>
#define size 1000
char rev(char []);
char new_line[size];
int j = 0;
int i =0;
int main ()
{
  char string[]=\"Game On\";
  rev(string);
  printf(\"Reversed rev string is %s\\n\",new_line);
  return 0;
}
char rev(char line[])
{
 while(line[i]!=\'\\0\')
  { 
    i++;
    rev(line);
    i--;
    new_line[j] = line[i];
    j++;
    return line[i];
  }
  return line[i];
}

芭隘的盘石

它将递归地反转原始字符串

void swap(string &str1, string &str2)
{
    string temp = str1;
    str1 = str2;
    str2 = str1;
}

void ReverseOriginalString(string &str, int p, int sizeOfStr)
{
    static int i = 0;
    if (p == sizeOfStr)
        return;

    ReverseOriginalString(str, s + 1, sizeOfStr);

    if (i <= p)
        swap(&str[i++], &str[p])
}

int main()
{
    string st = \"Rizwan Haider\";

    ReverseOriginalString(st, 0, st.length());
    std::cout << \"Original String is Reversed: \" << st << std::endl;

    return 0;
}

要回复问题请先登录或注册

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

18 个回复

发起人

reverse

c++

recursion

问题状态

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

与内容相关的链接

18 个回复

发起人

reverse

c++

recursion

问题状态