Forum de l’article
ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.
En fait je n’avais pas bien réfléchi. La hauteur moyenne de l’arbre d’appels (c’est-à-dire l’espérance de l’espace nécessaire sur la pile) est exactement la hauteur moyenne d’un ABR aléatoire. Cette quantité a bien sûr été étudiée, et on montre assez facilement qu’elle est logarithmique en $n$ (et même inférieure à $3\log_2(n)$). Je ne connais pas la variance, mais elle est petite.
Conclusion : la limite de 1000 stack frames en Python (qu’on peut modifier dynamiquement, d’ailleurs) n’est pour rien dans l’histoire ! Évidemment, essayer de manipuler de tels tableaux en Python « pur » (sans Numpy ou autre) reste une mauvaise idée, j’en conviens.
Bonjour, merci de vos contributions, elles sont en ligne. bc me dit :
$ bc -l
bc 1.07.1
l(200000000)
19.11382792451231078156
Donc ce n’est pas la profondeur de l’arbre de récursion, mais bien
probablement, comme vous le dites, l’encombrement de la mémoire,
et à force de page faults...
Bien à vous !