Re: Loupé

Justement si, une optimisation sur la pile d'appel car il estime qu'on risque de partir en stack overflow, ou qu'on perd trop de temps en changement de contexte.

Je ne vois pas trop cela dans son pseudo-code : il teste si l'appel est récursif et il empile, puis ne dépile que dans le cas contraire. On risque le débordement de pile. Mais c'est peut être moi qui ne comprend pas ce qu'il veut faire, je trouve qu'il ne s'exprime pas clairement.

Après ce n'est pas tant une question d'optimisation, contrairement à ton exemple. Pour moi, une fonction récursive terminale doit être compilée en consommant un espace constant sur la pile, sinon le compilateur est buggé. Je ne considère pas cela comme une optimisation mais comme une obligation sur le schème de compilation à utiliser.

Ton exemple est simple à écrire comme il faut, sans compter sur une optimisation du compilateur. Je le fais en OCaml :

let count n =
 let show i = if i mod 10_000 = 0 then (print_int i; print_newline ()) in
 let rec loop acc = function
 | 0 -> acc
 (* ici l'appel récursif est terminal *)
 | i -> show i; loop (acc + 1) (i - 1)
 in loop 0 n
;;

Le code récursif, correctement compilé, est équivalent à celui-ci avec un boucle for :

let count_for n =
 let show i = if i mod 10_000 = 0 then (print_int i; print_newline ()) in
 for i = n downto 0 do
 show i
 done;
 n
;;

Quelque soit le code choisi, il n'y a aucun risque de saturer la pile.

Je ne dis pas qu'il faut faire du récursif, souvent on peur remplacer par de l'itératif sans que ça alourdisse le code, mais remplacer tout appel récursif, juste par principe, avant même qu'un problème ait été levé, le tout via des solutions lourdes et compliqué rends rapidement le code visé difficile à maintenir.

Comme dit par uso dans le fil, cela dépend du langage utilisé et de ses idiomes. L'écriture de code récursif est tout un art. En OCaml, la plupart du temps on ne peut écrire du code que de manière récursive. Par exemple, la fonction qui itère une autre fonction (par effet de bords) sur les listes ne peut être écrite qu'ainsi :

let rec iter f = function
 | [] -> ()
 | hd :: tl -> f hd; iter f tl
;;

Exemple d'usage :

List.iter print_int [1; 2; 3];;
(* retour de l'appel *)
123

La fonction est terminale récursive et aura un code compilé équivalent à celui avec une boucle for ou while d'un langage impératif.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.