Сторнирование строки в C ++ (с использованием рекурсии)

Question

#include <iostream>
#include <string>
using namespace std;
void ReverseString(string &S, int size)
{
    static int start = 0;
    if (start == size - 1 || start == size)
    {
        return;
    }
    else
    {
        swap(S[start++], S[size - 1]);
        ReverseString(S, size - 1);
    }
}
int main()
{
    cout << "enter a string to reverse" << endl;
    string s;
    getline(cin, s);
    cout << "Before Reversing" << endl;
    cout << s << endl;
    ReverseString(s, s.size());
    cout << "After Reversing" << endl;
    cout << s << endl;
    return 0;
}

Я пытаюсь прибить как можно больше рекурсий, и я пытался перевернуть строку, используя рекурсию, сначала я не знал, как это сделать, пробовал много разных способов сделать это, но я видел примеры кода при перестановке строк, но ни один из них не имел смысла для меня, поэтому я сделал свой собственный, но не совсем уверен в этом, просто спрашиваю мнение, чисто ли оно и функционально ??

Спасибо

Answer 1

Использование функции local static в рекурсивной функции является плохой идеей. Рекурсивные функции должны получать все свое состояние в качестве входных аргументов.

Вот упрощенная версия, которая делит лог c на две функции.

void ReverseString(string &S, int start, int end)
{
   if ( start < end )
   {
      swap(S[start], S[end - 1]);
      ReverseString(S, start+1, end - 1);
   }
}

void ReverseString(string &S)
{
   ReverseString(S, 0, S.size());
}

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

Вот пример программы

#include <iostream>
#include <string>

using namespace std;

void ReverseString(string &S, int start, int end)
{
   if ( start < end )
   {
      swap(S[start], S[end - 1]);
      ReverseString(S, start+1, end - 1);
   }
}

void ReverseString(string &S)
{
   ReverseString(S, 0, S.size());
}

int main()
{
    string s = "The string to reverse" ;

    cout << "Before Reversing" << endl;
    cout << s << endl;

    ReverseString(s);
    cout << "After Reversing" << endl;
    cout << s << endl;

    ReverseString(s, 0, 7);
    cout << "After Reversing a subset" << endl;
    cout << s << endl;
    return 0;
}

и ее вывод

Before Reversing
The string to reverse
After Reversing
esrever ot gnirts ehT
After Reversing a subset
reverse ot gnirts ehT

См. Это работает на https://ideone.com/9nMlsP.

Answer 2

это ... функционально ??

Если под "функционалом" вы подразумеваете "это работает", то вы говорите мне.

Если вы имеете в виду «функциональный» как в «функциональном» стиле программирования, то нет, это не так. В функциональном стиле вы не изменяете аргументы на месте, а вместо этого возвращаете новое значение. Также полагаться на глобальное состояние (т. Е. Объекты c) очень антифункционально.

Вот пример:

std::string
ReverseString(std::string_view sv)
{
    if (sv.empty())
        return "";
    std::string_view x  = sv.substr(0, 1)
    std::string_view xs = sv.substr(1);
    return ReverseString(xs) + x;
}

// usage
s = ReverseString(s);

---

В будущем, если Pattern сопоставление было введено в язык, а затем его можно было бы написать так:

std::string
ReverseString(std::string_view sv)
{
    inspect(sv) {
        "":      return "";
        [x:xs]:  return ReverseString(xs) + x;
    }
}

Однако в текущем предложении не предлагается вводить поддержку сопоставления диапазонов, как это, так что это весьма теоретически.

Answer 3

Любой может перевернуть строку по одному символу за раз, но гораздо круче будет перевернуть каждую треть строки и поменять местами внешние. Это снижает глубину стека, а также приводит к путанице среди конкурентов.

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

void ReverseRegion(string &s, int start, int sz)
{
  // regions < 2 need no action
  if (sz == 2) {
    char tmp = s[start];
    s[start] = s[start+1];
    s[start+1] = tmp;
  } else if (sz > 2) {
    int s3 = sz/3;
    ReverseRegion(s, start, s3);
    string tmp = s.substr(0,start) + s.substr(start+sz-s3,s3) + s.substr(start+s3, sz-2*s3) + s.substr(start,s3) + s.substr(start+sz);
    // cout << "do: " << tmp << "\n";
    s = tmp;
    ReverseRegion(s, start+s3, sz-2*s3);
    ReverseRegion(s, start, s3);
  }
}


void ReverseString(string &S)
{
  ReverseRegion(S, 0, S.size());
}

int main()
{
    cout << "enter a string to reverse" << endl;
    string s;
    getline(cin, s);
    cout << "Before Reversing" << endl;
    cout << s << endl;
    ReverseString(s);
    cout << "After Reversing" << endl;
    cout << s << endl;
    return 0;
}

Answer 4

Ваша функция с переменной stati c может быть вызвана только один раз, потому что после ее рекурсивных вызовов переменная stati c start не будет равна 0, как это требуется. Таким образом, функция не является «функциональной».

Вот демонстрационная программа, которая показывает, как можно написать функцию с использованием переменной stati c и без использования переменной stati c.

#include <iostream>
#include <string>
#include <utility>

void ReverseString1( std::string &s )
{
    static std::string::size_type i = 0;

    if ( not ( s.size() - 2 * i < 2 ) )
    {
        std::swap( s[i], s[s.size() - i - 1] );

        ++i;
        ReverseString1( s );
        --i;
    }
}

void ReverseString2( std::string &s, std::string::size_type pos = 0 )
{
    if ( not ( s.size() - 2 * pos < 2 ) )
    {
        std::swap( s[pos], s[s.size() - pos - 1] );
        ReverseString2( s, pos + 1 );
    }
}

int main() 
{
    std::string s( "Hello World!" );

    std::cout << s << '\n';

    ReverseString1( s );

    std::cout << s << '\n';

    ReverseString2( s );

    std::cout << s << '\n';

    return 0;
}

Вывод программы

Hello World!
!dlroW olleH
Hello World!

Answer 5

Локальные данные c переменные опасны. Так как их состояние останется между вызовами функций. В моем подходе я использовал slen в качестве длины строки и currentIndex в качестве последнего поменяемого индекса в строке. Поскольку достаточно поменять местами до середины строки, конечный случай sh - это когда (currentIndex == slen/2). В качестве примера я также добавил несколько тестовых случаев (четная длина, нечетная длина, нулевой регистр и палиндром)

#include <iostream>
#include <string>
using namespace std;
void ReverseString(string &S, int currentIndex, int slen)
{
    if (slen / 2 == currentIndex) return;

    swap(S[currentIndex], S[slen - 1 - currentIndex]);
    currentIndex++;

    ReverseString(S, currentIndex, slen);
}

void testReverseString() {
    string s = ""; 
    ReverseString(s, 0, s.length());
    assert(s == "");

    s = "ahmet"; 
    ReverseString(s, 0, s.length());
    assert(s == "temha");

    s = "ahaha"; 
    ReverseString(s, 0, s.length());
    assert(s == "ahaha");

    s = "haha"; 
    ReverseString(s, 0, s.length());
    assert(s == "ahah");
}

int main()
{
    testReverseString();
    return 0;
}