inversion de tableau avec une méthode récursive

Le
aquilon11
Bonjour


J'ai réalisée une fonction d'inversion de tableau par une méthode
itérative, cela fonction.

Je voudrai réaliser la même fonction avec une méthode récursive, mai=
s
j'ai un problème de concaténation de tableau



#methode iterative
def inversTab1(tab):
i=0
while i < len(tab)/2:
elm = tab[i]
tab[i] = tab[-(i+1)]
tab[-(i+1)] = elm
i = i + 1

#methode recursive
def inversTab2(tab):
if len(tab) > 1:
tab = tab[0] + inversTab2(tab[1:-2]) + tab[-1]



tableau = [12, 15, 50, 0, 100, 200, 0, 0, 4]
print tableau
inversTab1(tableau)
print tableau
inversTab2(tableau)
print tableau

Merci de votre assistance
Questions / Réponses high-tech
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Bruno Desthuilliers
Le #1458321
Bonjour


J'ai réalisée une fonction d'inversion de tableau


tab = list('square wheel')
tab
['s', 'q', 'u', 'a', 'r', 'e', ' ', 'w', 'h', 'e', 'e', 'l']



tab.reverse()
tab
['l', 'e', 'e', 'h', 'w', ' ', 'e', 'r', 'a', 'u', 'q', 's']



list(reverse(tab))
Traceback (most recent call last):



File "<stdin>", line 1, in <module>
NameError: name 'reverse' is not defined
list(reversed(tab))
['s', 'q', 'u', 'a', 'r', 'e', ' ', 'w', 'h', 'e', 'e', 'l']








Mais je suppose que c'est un exo d'algo, pas un besoin réel !-)

par une méthode
itérative, cela fonction.

Je voudrai réaliser la même fonction avec une méthode récursive, mais
j'ai un problème de concaténation de tableau



#methode iterative
def inversTab1(tab):
i=0
while i < len(tab)/2:
elm = tab[i]
tab[i] = tab[-(i+1)]
tab[-(i+1)] = elm
i = i + 1




#methode recursive
def inversTab2(tab):
if len(tab) > 1:
tab = tab[0] + inversTab2(tab[1:-2]) + tab[-1]
# manquait ça

return tab



tableau = [12, 15, 50, 0, 100, 200, 0, 0, 4]
print tableau
inversTab1(tableau)
print tableau
inversTab2(tableau)
print tableau

Merci de votre assistance


Ca aurait été mieux si tu avais précisé quel était exactement ton
problème...



Pierre Maurette
Le #1465990
Bonjour


J'ai réalisée une fonction d'inversion de tableau par une méthode
itérative, cela fonction.

Je voudrai réaliser la même fonction avec une méthode récursive, mais
j'ai un problème de concaténation de tableau



#methode iterative
def inversTab1(tab):
i=0
while i < len(tab)/2:
elm = tab[i]
tab[i] = tab[-(i+1)]
tab[-(i+1)] = elm
i = i + 1

#methode recursive
def inversTab2(tab):
if len(tab) > 1:
tab = tab[0] + inversTab2(tab[1:-2]) + tab[-1]



tableau = [12, 15, 50, 0, 100, 200, 0, 0, 4]
print tableau
inversTab1(tableau)
print tableau
inversTab2(tableau)
print tableau

Merci de votre assistance


Je comprends très bien que l'on puisse avoir envie d'utiliser une
méthode dans un but pédagogique. Je vous signale néanmoins:
tableau = tableau[::-1]
ou mieux:
tableau.reverse()

Il se trouve que la récursivité n'est pas ici à mon sens une très bonne
solution. Et puis il vous faut définir votre récursivité. Là, vous
joutez à un élément (un entier) le retour de inversTab2(), c'est à dire
None.

Vous pourriez peut-être faire artificiellement une fonction récursive,
avec une fonction-lanceur pour respecter l'interface:

#methode recursive
def inversTab2(tab):
__inversTab2(tab, len(tab))

def __inversTab2(tab, n):
if n > len(tab) / 2:
__inversTab2(tab, n-1)
elm = tab[len(tab) - n]
tab[len(tab) - n] = tab[n - 1]
tab[n - 1] = elm


--
Pierre Maurette

Bruno Desthuilliers
Le #1465989
Bonjour


J'ai réalisée une fonction d'inversion de tableau


(snip)

#methode recursive
def inversTab2(tab):
if len(tab) > 1:
# pb ici aussi:


#tab = tab[0] + inversTab2(tab[1:-2]) + tab[-1]
tab = [tab[0]] + inversTab2(tab[1:-2]) + [tab[-1]]

# manquait ça
return tab



Pierre Maurette
Le #1465988
Bonjour


J'ai réalisée une fonction d'inversion de tableau


(snip)

#methode recursive
def inversTab2(tab):
if len(tab) > 1:
# pb ici aussi:


#tab = tab[0] + inversTab2(tab[1:-2]) + tab[-1]
tab = [tab[0]] + inversTab2(tab[1:-2]) + [tab[-1]]

# manquait ça
return tab



Hum. Pas l'impression que ça fonctionne. On peut éventuellement faire
ça:

#methode recursive
def inversTab2(tab):
if len(tab) > 1:
return [tab[-1]] +inversTab2(tab[1:-1]) + [tab[0]]
return tab

Mais on n'inverse plus "en place", et qui plus est sauf erreur de ma
part on crée une palanquée de tableaux intermédiares.

--
Pierre Maurette



Pierre Maurette
Le #1465987

[...]

#methode recursive
def inversTab2(tab):
__inversTab2(tab, len(tab))

def __inversTab2(tab, n):
if n > len(tab) / 2:
__inversTab2(tab, n-1)
elm = tab[len(tab) - n]
tab[len(tab) - n] = tab[n - 1]
tab[n - 1] = elm


Et pour frimer le prof, qui aura au moins compris que vous savez
utiliser internet, une façon délicieusement pythonesque de faire le
swap:

def __inversTab2(tab, n):
if n > len(tab) / 2:
__inversTab2(tab, n-1)
tab[len(tab) - n], tab[n - 1] = tab[n - 1], tab[len(tab) - n]

--
Pierre Maurette

aquilon11
Le #1465986
Je vous remercie de ces précisions, je suis tout à fait d'accord sur
le fait que la version récursive consomme plus de mémoire que la
version itérative.

Mai pour apprendre un langage, je pense qu'il vaux mieux travail sur
de petit exercices en utilisant plusieurs algorithme, que de faite un
gros programme avec 80% d'interface opérateur.

PS : je n'aime pas perl
Bruno Desthuilliers
Le #1465985
Bonjour


J'ai réalisée une fonction d'inversion de tableau


(snip)

#methode recursive
def inversTab2(tab):
if len(tab) > 1:
# pb ici aussi:


#tab = tab[0] + inversTab2(tab[1:-2]) + tab[-1]
tab = [tab[0]] + inversTab2(tab[1:-2]) + [tab[-1]]

# manquait ça
return tab



Hum. Pas l'impression que ça fonctionne.


Je n'avais d'autre ambition que de corriger une paire d'erreurs
évidentes - pour ce qui est de la correction de l'algo (et de sa
pertinence), c'est l'affaire de l'OP !-)

On peut éventuellement faire ça:

#methode recursive
def inversTab2(tab):
if len(tab) > 1:
return [tab[-1]] +inversTab2(tab[1:-1]) + [tab[0]]
return tab

Mais on n'inverse plus "en place", et qui plus est sauf erreur de ma
part on crée une palanquée de tableaux intermédiares.


Tout à fait. Mais de toutes façons, quite à faire de la récursion,
autant éviter les effets de bords.




Eric Brunel
Le #1506678
On Mon, 10 Mar 2008 11:44:46 +0100,
Bonjour


J'ai réalisée une fonction d'inversion de tableau par une méthode
itérative, cela fonction.

Je voudrai réaliser la même fonction avec une méthode récursive, mais
j'ai un problème de concaténation de tableau
[snip]

#methode recursive
def inversTab2(tab):
if len(tab) > 1:
tab = tab[0] + inversTab2(tab[1:-2]) + tab[-1]


Comme le disait Bruno, quitte à faire du récursif, autant partir dans le
"full-fonctionnel" et éviter les effets de bord. Et là, mes antiques cours
de Lisp vont me servir:

def invert_list(l1, l2=()):
if not l1:
return list(l2)
else:
return invert_list(l1[1:], [l1[0]] + list(l2))

(NB: c'est un abominable gâchis de ressouces, je sais...)

Question à 0.02€: pourquoi ça marche? ;-)

HTH quand même...
--
python -c "print ''.join([chr(154 - ord(c)) for c in
'U(17zX(%,5.zmz5(17l8(%,5.Z*(93-965$l7+-'])"

Méta-MCI \(MVP\)
Le #1542390
Bonsoir !

Puisque le ton est au tordu :

def rrlist():
lret=[]
def r(l):
lret.insert(0,l[0])
if len(l)>2:
r(l[1:])
else:
lret.insert(0,l[1])
return r,lret

inverse,reverselist=rrlist()
a=[11,22,33,44,55]
inverse(a)
print reverselist


OK, c'est tordu, mais avec un soupçon de récursivité (ouf, sauvé ! ?)


@+

MCI
Publicité
Poster une réponse
Anonyme