Forum de l’article

Python, Scheme, C

modération a priori

Ce forum est modéré a priori : votre contribution n’apparaîtra qu’après avoir été validée par un administrateur du site.

Qui êtes-vous ?
Votre message

Pour créer des paragraphes, laissez simplement des lignes vides.

Lien hypertexte

(Si votre message se réfère à un article publié sur le Web, ou à une page fournissant plus d’informations, vous pouvez indiquer ci-après le titre de la page et son adresse.)

Rappel de la discussion
Python, Scheme, C
Jean-Baptiste Bianquis - le 26 juin 2020

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.

Python, Scheme, C
Laurent Bloch - le 26 juin 2020

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 !