Bienvenue sur IndexError.

Ici vous pouvez poser des questions sur Python et le Framework Django.

Mais aussi sur les technos front comme React, Angular, Typescript et Javascript en général.

Consultez la FAQ pour améliorer vos chances d'avoir des réponses à vos questions.

RecursionError en comparant des listes récursives

+1 vote

C'est juste une curiosité :

>>> foo = []
>>> bar = [foo]
>>> foo.append(bar)
>>> foo == bar
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded in comparison

Pourquoi ça donne une erreur ?
(Testé sur python 3.6.7)

demandé 24-Nov-2018 par Linekio (124 points)

2 Réponses

+1 vote

Prends cet exemple :

>>> foo = []
>>> bar = [foo]
>>> foo
[]
>>> bar
[[]]
>>> foo.append(1)
>>> foo
[1]
>>> bar
[[1]]

Quoi que tu ajoutes dans foo sera visible dans bar car il contient une référence vers foo.

Du coup, quand tu fais foo.append(bar), chacune des listes va s'inclure mutuellement, ce qui donne une RecursionError.
D'ailleurs, l'interpréteur Python te prévient de la profonde récursivité (via l'ellipsis) :

>>> foo.append(bar)
>>> foo
[[[...]]]
>>> bar
[[[...]]]

Mais ceci depuis Python 3.6.5 seulement :

repr() on a dict containing its own values() or items() no longer raises RecursionError; OrderedDict similarly. Instead, use ..., as for other recursive structures. Patch by Ben North.

répondu 24-Nov-2018 par Tiger-222 (1,124 points)
edité 24-Nov-2018 par Tiger-222

J'ai bien compris que je fais des listes récursives, mais c'est valide.
foo.append(bar) ne donne pas d'erreur. C'est la comparaison foo == bar qui plante. Tout comme foo[0] == foo, etc...

0 votes

Rien n’empêche une liste d’être récursive. Comparer deux structures récursives ne va rien donner de bon: la comparaison va se faire récursivement sur les éléments, chaque comparaison provoquant un nouvel appel de fonction, jusqu’à ce que la pile d'appel explose...

Une version simplifiée de ton exemple serait:

l1 = []
l1.append(l1)
l2 = []
l2.append(l2)
l1 == l2  # RecursionError

Tu peux montrer que la liste se contient elle même:

l1 is l1[0] # True
# ...
l1 is l1[0][0][0][0][0] # True
# etc...

On peut s'amuser a faire pareil avec des dictionnaires:

d1 = {}
d1[0] = d1
d2 = {}
d2[0] = d2
d1 == d2  # RecursionError

La raison pour laquelle l1 == l1 ne provoque pas de RecursionError est que la comparaison vérifie tout d'abord l’identité, et renvoie True dans ce cas.

Plus curieux, on peut obtenir des résultats a priori surprenants:

>>> l = []
>>> l.append(l)
>>> l
[[...]]
>>> [l]
[[[...]]]
>>> l == [l]
True

La raison est que la comparaison se fait élément par élément, or le premier élément de [l] est l, ce qui est aussi le cas pour l vu qu'elle est récursive, le résultat est donc True.

répondu 29-Nov-2018 par yoch (2,510 points)

Ok je comprend, la comparaison est récursive c'est logique.
Et dans ce dernier cas, il doit commencer par tester id(l) == id([l]), ou bien l is [l] mais c'est pareil je crois.

C'est pourquoi dans mon exemple foo == bar[0] renvoie True aussi.

...