Re: Loupé

et des choses qui s'expriment simplement en récursif deviennent un enfer en itératif.

Non. C’est juste que tu n’as pas appris et que tu n’as pas l’habitude. C’est tout mon propos. Problème de formation. Un code récursif n’explicite pas les éléments de ta pile et peut poser quelques inconvénients à l’implémentation (variable locales & arguments sont confondus avec les éléments de ta pile, obligation souvent d’avoir une fonction chapeau pour initier la récursion).

Un algo récursif définit explicitement les éléments de ta pile. En C par exemple j’ai pris pour habitude d’avoir une struct el _stack[SIZE], *stack=_stack;. Mon struct el est explicite donc plus lisible, d’autant plus qu’il va être souvent non spécifique (dans le parcours d’un arbre/graphe par exemple c’est les node du graphe). Empiler et dépiler sont des opérations on ne peut plus simple que stack++ ou stack-- où tu transmet/alimente les valeurs nécessaires (arguments et valeur de retour sur la pile) et contrôle les dépassements avec la possibilité d’allocation dynamique (l’empilage et le dépilage sont implémentées comme des petites macro ou fonction inline).

Tu as aussi une grosse méconnaissance des langages type C. Car c’est exactement ce qu’ils mettent un œuvre, un algo récursif avec comme pile la fameuse "call stack". Donc rien d’insurmontable.

L’appel à une fonction ce n’est rien d’autre qu’un empilage/rebouclage.
Le retour d’une fonction un dépilage. Sans avoir rien à tordre, ton appel récursif est trivialement transposable en un pseudo-code récursif de la forme —très— universelle suivante :

appel:
 ...
retour:
 ...
decision:
 si appel récursif:
 {
 empiler
 goto appel
 }
 sinon:
 {
 dépiler
 si la pile est vide on a terminé.
 sinon goto retour
 }
...

Note qu’on fait sans les goto en général, mais c’est pour montrer qu’on peut être plus universel encore que l’appel récursif — car là où un retour à l’appelant suit forcément l’appel à une fonction (le pointeur d’instruction est mis sur la pile puis dépilé), le goto/label est bien plus souple (la forme que je présente n’est pas possible avec une fonction récursive — il faut tordre l’algo).

C'est un drame de se dire que le codeur de base fait mieux que le compilo pour optimiser

J’aimerai sincèrement que soit faite la démonstration que le compilo est capable de distinguer très exactement la pile de ton algo de la call stack et de les séparer. S’il y arrive, la call stack ne doit plus être manipulée lors de la récursion et c’est tout l’enjeu. En commençant par bien distinguer les arguments de ta fonction récursive, entre ceux qui participent à la récursivité de ceux qui sont invariants dans la récursion, ensuite en étant capable de faire sauter la limitation en taille de la call stack, idem les variables locales qui n’ont pas forcément à être empilées.

Et pas uniquement dans le cas de la mal nommée "récursion" terminale (qui est toujours trivialement transposable en itératif ceci dit en passant).

Et non c’est pas du tout lisible : si je lis un appel récursif je m’attend à un algo récursif, pas un truc oui-mais-en-fait-non. Il s’agit aussi d’évaluer la complexité et la performance d’un bout de code (itératif : je sais que je suis en O(n), récursion je m’attends à un truc du genre O(nlog(n))), et de ne pas se rajouter de la charge mentale (il est beaucoup plus difficile d’appréhender le comportement d’un code buggé qui a une pile, donc j’aime savoir si la pile est vraiment justifiée).

Qui plus est il ne s’agit pas d’optimiser, mais précisément de ne pas créer un code inutilement complexe pour le compilo. En plus de ça, dès que tu vas vouloir faire des algos sur des données un minimum couillues tu vas vouloir contrôler ta taille de pile (donc exit la call stack).