Напишите рекурсивную функцию, которая переворачивает входную строку

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

Вместо этого я объясню сам рекурсивный алгоритм.Возьмите пример «input», который должен производить «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
}

Рекурсивная функция должна иметь следующие свойства

• Она должна вызывать себя снова
• Она должна иметь условие, когдарекурсия заканчивается.В противном случае у вас есть функция, которая вызовет переполнение стека.

Эта рекурсивная функция в основном создает строку последнего символа, а затем снова вызывает себя с остальной частью строки, исключая последний символ.Реальное переключение происходит в последней строке, где возвращается последний + обратный.Если бы все было наоборот, ничего бы не случилось.

Это очень неэффективно, но работает, чтобы показать концепцию.

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

Answer 4

Я не буду писать полноценный алгоритм для вас, но вот подсказка:

Как насчет поменять местами два крайних символа, а затем применить то же самое к символам в середине?

О, и если эта книга действительно предложила string reverse(string str) в качестве соответствующей подписи функции для этого, выбросьте ее и вместо этого купите хорошую книгу .

Answer 5

Вот моя версия рекурсивной функции, которая переворачивает входную строку:

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
}

Answer 6

Самый короткий и простой

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

Answer 7

Я сделал что-то вроде этого, он сделал перестановку на месте.Я взял две переменные, которые пересекают строку от двух крайних концов до центра строки, и когда они перекрываются или равны друг другу, обращение прекращается.

Возьмем пример: input string str = "abcd" и вызовем функцию как

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

и рекурсивно увеличивать / уменьшать указатели переменных.Сначала указатели указывают на 'a' и 'd' и меняют их местами, затем они указывают на 'b' и 'c' и меняют их местами.В конечном итоге i >= j, который требует, чтобы базовый случай был истинным, и, следовательно, рекурсия завершается.Основной вопрос для этого вопроса - передать входную строку в качестве ссылки.

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

Answer 8

вы можете реализовать свой собственный реверс, аналогичный 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);
}

Answer 9

Во всех существующих решениях было слишком много кода, который на самом деле ничего не делал, поэтому вот мое мнение:

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

---

P.S. Я наткнулся на этот вопрос, пытаясь найти способ C ++ для std::string того, что s+1 для char * в C; не пройдя весь маршрут s.substr(1, s.length()-1), который выглядит слишком некрасиво. Оказывается, есть std::string::npos, что означает до конца строки, и это уже значение по умолчанию для второго аргумента, поэтому достаточно s.substr(1) (плюс, он также выглядит более эффективным и наравне с простым s + 1 в С).

---

Обратите внимание, однако, что рекурсия в общем случае не масштабируется при увеличении входных данных, если только компилятор не может выполнить то, что известно как оптимизация хвостовой рекурсии. (На рекурсию редко обращаются в императивных языках.)

Однако, чтобы активировать оптимизацию хвостовой рекурсии, обычно требуется, чтобы (0) рекурсия происходила только внутри оператора return и чтобы (1) никакие дальнейшие операции не выполнялись с результат рекурсивного обратного вызова в родительской функции.

Например, в приведенном выше случае + s[0] логически выполняется родителем после завершения дочернего вызова (и, вероятно, будет так, даже если вы пойдете по более уродливому маршруту s[s.length()-1] +), поэтому он может очень хорошо, чтобы большинство компиляторов не выполняли хвостовую рекурсию-оптимизацию, что делает функцию очень неэффективной на больших входах (если не нарушена из-за исчерпания кучи).

(Для чего я пытался написать более дружественное к хвосту рекурсивное решение (убедившись, что возвращаемый результат вырастет через аргумент самой функции), но разборка получающегося двоичного файла, кажется, предполагает, что это более сложный, чем в императивных языках, таких как C ++, см. gcc: нет ли хвостовой рекурсии, если я верну std :: string в C ++? .)

Answer 10

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