Écrire une fonction récursive qui inverse la chaîne d'entrée

J'ai deux minutes, donc je vais plutôt expliquer l'algorithme récursif lui-même. Prenez, par exemple, "entrée", ce qui devrait produire "tupni". Vous pouvez inverser la chaîne de manière récursive par

• Si la chaîne est vide, ou un seul caractère, le retourner inchangé.
• Autrement,
  1. Supprimer le premier caractère.
  2. Inverser la chaîne restante.
  3. Ajouter le premier caractère au-dessus de la chaîne inversée.
  4. De retour de la nouvelle chaîne.

OriginalL'auteur David Harkness

Juste pour suggérer une meilleure façon de gérer la récursivité:

Chaîne de renversement à l'aide de la récursivité en 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;
}

OriginalL'auteur totjammykd

Voici ma version d'une fonction récursive qui renverse la chaîne d'entrée:

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
}

OriginalL'auteur Ann Orlova

1 de la ligne de solution récursive:

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

Vous l'appeler comme ceci:

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

OriginalL'auteur PieThon

Toutes les solutions existantes en avait beaucoup trop de code qui n'a pas vraiment quoi que ce soit, donc, voici mon point de vue:

#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. je suis tombé sur cette question en essayant de trouver une C++ moyen pour std::string de ce s+1 pour un char * en C est; sans aller l'ensemble du parcours de s.substr(1, s.length()-1), qui a l'air trop moche. S'avère, il y a std::string::npos, ce qui signifie que jusqu'à la fin de la chaîne, et c'est déjà la valeur par défaut pour le deuxième argument, donc, s.substr(1) est assez (et en plus, il a également semble plus efficace et sur le pair avec la simple s + 1 en C).

Noter, cependant, que la récursivité en général n'a pas d'échelle de l'entrée grandit, à moins que le compilateur est capable de faire ce qui est connu comme la queue de la récursivité d'optimisation. (Récursivité est rarement invoqué dans des langages impératifs.)

Toutefois, pour que la queue de la récursivité d'optimisation pour obtenir activé, il est généralement nécessaire que, (0), la récursion ne se produit que dans le return déclaration, et que, (1), pas d'autres opérations sont effectuées avec le résultat de l'appel récursif de retour dans la fonction parent.

E. g., dans le cas ci-dessus, le + s[0] est logiquement fait par le parent de l'enfant appel se termine (et probablement il serait donc, même si vous allez plus hideuses s[s.length()-1] + route), alors, il pourrait ainsi prévenir la plupart des compilateurs de faire un tail-recursion-est de l'optimisation, et donc de faire de la fonction très efficace sur de grandes entrées (si ce n'est carrément cassé à cause d'un tas d'épuisement).

(Pour ce que ça vaut, j'ai tenté d'écrire un plus tail-recursion-solution à l'amiable (en prenant soin de faire croître le résultat de retour par le biais d'un argument à la fonction elle-même), mais le démontage de la binaire résultant semble suggérer que c'est plus impliqué que dans les langages comme C++, voir gcc: il n'y a pas de queue de récursivité si je retourne std::string en C++?.)

OriginalL'auteur cnst

J'ai fait quelque chose comme cela, il ne le renversement en place. J'ai pris deux variables qui traverse la chaîne à partir de deux extrémité au centre de la chaîne et quand ils se chevauchent ou égal à l'autre, puis l'inversion se termine.

Prendre un exemple: entrée string str = "abcd" et appeler la fonction comme

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

et incrémenter/décrémenter la variable pointeurs de manière récursive.
D'abord les pointeurs points de 'a' et 'd' et swap, ils le point de 'b' et 'c' et l'échange. Finalement i >= j qui appelle pour le cas de base pour être vrai, et donc la récurrence s'arrête. Le principal tenir à l'écart de cette question est de passer de la chaîne d'entrée comme référence.

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

OriginalL'auteur Marco167

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

OriginalL'auteur user3674936

voici mes 3 chaîne de ligne de revers

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

OriginalL'auteur SRedouane