Je dois diviser une chaîne, par exemple 'star' en une liste telle que ['s','t','a','r'] et je dois le faire de manière récursive. Je sais comment faire cela de manière itérative mais pas récursive.

Ci-dessous, mon code pour le faire, mais cela ne fonctionne pas à juste titre.

def explode(S):
    res = []
    res.append(S[0])
    if len(S)==1:
        return res
    else:
        res.append(explode(S[1:]))
    return res

La sortie que j'obtiens est:

['s', ['t', ['a', ['r']]]]

Comment puis-je réparer ça? Y a-t-il un exemple à partir duquel je peux mieux apprendre la récursivité parce que cela ne fonctionne clairement pas.

1
swom bhai 3 oct. 2021 à 04:09

4 réponses

Meilleure réponse

Typiquement avec la récursivité, vous devriez d'abord penser au cas de base - ici une chaîne vide. Ensuite, prenez une partie de l'entrée et récursez sur le reste.

Dans ce cas, vous n'avez même pas besoin d'instancier manuellement une liste... faites-le simplement dans le cas de base et vous évitez complètement d'étendre/ajouter :

def explode(s):
    if not s:                       # base case
        return []
    head, *rest = s                 # take a piece
    return [head] + explode(rest)   # pass the rest back in

explode('star')
# ['s', 't', 'a', 'r']
3
Mark 3 oct. 2021 à 01:16

Essayez extend au lieu de append :

def explode(S):
    res = []
    res.append(S[0])
    if len(S)==1:
        return res
    else:
        res.extend(explode(S[1:]))
    return res

Production:

>>> explode('star')
['s', 't', 'a', 'r']
>>> 

Mais vous pouvez simplement utiliser la fonction list :

>>> list('star')
['s', 't', 'a', 'r']
>>> 

Une autre idée récursive qui est similaire à celle de @Mark mais avec des générateurs :

def explode(S):
    if not S:
        return []
    it = iter(S)
    return [next(it)] + explode(list(it))

Ex:

>>> explode('star')
['s', 't', 'a', 'r']
>>> 
1
U12-Forward 3 oct. 2021 à 01:21

Vous pouvez le faire avec un paramètre par défaut qui vous donne l'indice du caractère à ajouter au résultat :

def explode(S,i=0):
    return [S[i]] + explode(S,i+1) if i<len(S) else []

print(explode('Hello World!'))
['H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l', 'd', '!']
0
Alain T. 3 oct. 2021 à 01:47

Un moyen simple de le faire serait de le convertir en liste.

Disons que vous avez une chaîne

s = "star"

La conversion d'une chaîne en liste peut être effectuée en utilisant list()

converted = list(s)
0
Agent47 3 oct. 2021 à 01:47