RecursionError en comparant des listes récursives

Question

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)

Answer 1

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.

Comments

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...

Answer 2

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.

Comments

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.