Python inversion d'une chaîne à l'aide de la récursivité

Je veux utiliser la récursivité pour inverser une chaîne de caractères en python de sorte qu'il affiche les caractères en arrière (j'.e "Bonjour" devient "olleh"/"o l l e h".

J'ai écrit un qui le fait de manière itérative:

def Reverse( s ):
    result = ""
    n = 0
    start = 0
    while ( s[n:] != "" ):
        while ( s[n:] != "" and s[n] != ' ' ):
            n = n + 1
            result = s[ start: n ] + " " + result
            start = n
    return result

Mais comment dois-je faire exactement cela de façon récursive? Je suis confus sur cette partie, surtout parce que je ne travaille pas avec python et la récursivité beaucoup.

Toute aide serait appréciée.

Est-ce devoirs?

OriginalL'auteur Eric | 2011-04-03

  1. 18
    def rreverse(s):
    if s == "":
        return s
    else:
        return rreverse(s[1:]) + s[0]

    (Très peu de gens le font lourds récursive traitement en Python, le langage de n'a pas été conçu pour cela.)

    Ok qui fonctionne mais comment fonctionne exactement la partie inférieure de travail? Vous êtes à l'appel de la fonction rreverse sur le 1er élément de la chaîne et de l'impression de l'0e élément. Comment fonctionne exactement le rreverse(s[1:]) incrémentée à chaque fois?
    appel récursif est faite sur la sous-chaîne de s à partir du deuxième élément de e.g S[1:] vous donne s sans le premier élément). Il est en ajoutant le résultat de l'appel récursif pour le premier caractère de s, par exemple, s[0].
    Quelle est la complexité
    La complexité est O(n)

    OriginalL'auteur Fred Foo

  2. 18

    Pour résoudre un problème de manière récursive, trouver un cas trivial qui est facile à résoudre, et de comprendre comment obtenir à ce cas trivial par décompose le problème dans le plus simple et le plus simple des versions de lui-même.

    Quelle est la première chose à faire pour inverser une chaîne de caractères? Littéralement, la première chose? Vous obtenez le dernier caractère de la chaîne, droit?

    Donc l'inverse d'une chaîne est le dernier caractère, suivie par l'inverse de tout ce mais le dernier caractère, qui est l'endroit où la récursivité. Le dernier caractère d'une chaîne de caractères peut être écrite comme x[-1] alors que tout mais le dernier caractère est x[:-1].

    Maintenant, comment voulez-vous "en bas"? Qui est, ce qui est le cas trivial vous pouvez résoudre sans récursivité? Une seule réponse est la chaîne de caractères, qui est la même avant et marche arrière. Donc, si vous obtenez une chaîne de caractères, vous avez terminé.

    Mais la chaîne vide est encore plus trivial, et quelqu'un pourrait passer que dans votre fonction, de sorte qu'il serait probablement préférable de l'utiliser à la place. Une chaîne de caractères peut, après tout, aussi être décomposé dans le dernier caractère et tout, mais le dernier caractère, c'est juste que tout, mais le dernier caractère est la chaîne vide. Donc, si nous nous occupons de la chaîne vide par un juste retour, nous sommes ensemble.

    Mettre tout cela ensemble et vous obtenez:

    def backward(text):
    if text == "":
        return text
    else:
        return text[-1] + backward(text[:-1])

    Ou en une seule ligne:

    backward = lambda t: t[-1] + backward(t[:-1]) if t else t

    Comme d'autres l'ont souligné, ce n'est pas la manière que vous le feriez normalement le faire en Python. Une solution itérative est va être plus rapide, et à l'aide de découpage à faire il va être encore plus rapide.

    En outre, Python impose une limite sur la taille de la pile, et il n'y a pas la queue d'appel d'optimisation, donc une solution récursive serait limitée à inverser les chaînes de seulement environ un millier de caractères. Vous pouvez augmenter Python taille de la pile, mais il y aura toujours une limite fixe, alors que d'autres solutions peuvent toujours manipuler une chaîne de caractères de longueur quelconque.

    OriginalL'auteur kindall

  3. 4

    Si ce n'est pas seulement des devoirs à faire à la question et que vous êtes en train d'essayer d'inverser une chaîne de caractères pour un plus grand objectif, il suffit de faire s[::-1].

    Fait amusant: Ce qui est parfois appelé un "Martien smiley".
    ou tout simplement reversed()
    reversed() ne fait pas ce que vous pensez que cela fonctionne. 🙂
    ^ w0w au moins expliquer
    ^ Peut-être que vous devriez au moins essayer vous-même? ".join( [i for i in inversé(s)]) est-ce que vous pensez que cela fonctionne, inversé retourne un inversée de l'objet que vous devez parcourir pour récupérer une chaîne de caractères.

    OriginalL'auteur bradley.ayers

  4. 1
    def reverse_string(s):
    if s: return s[-1] + reverse_string(s[0:-1])
    else: return s

    ou

    def reverse_string(s):
    return s[-1] + reverse_string(s[0:-1]) if s else s

    OriginalL'auteur Jarek Przygódzki