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 par Linekio (112 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 par Tiger-222 (884 points)
edité 24-Nov par Tiger-222
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 par yoch (2,506 points)
...