Bin de ce que je me souviens de mes cours, une fonction récursive est
récursive terminale si tous les appels récursifs ne sont pas dans un calcul (on dépile ou on s'arrête).
Si on prend l'exemple habituel de la factorielle :
Bloc de code:
int fact(int n) {
if (n <= 1) {
return 1;
}
return n * fact(n-1);
}
Cette fonction n'est pas récursive terminale car on ne va revenir du premier appel récursif que lorsqu'on atteint le cas de base. Et donc on va empiler n appels récursifs, ce qui n'est pas bon.
Par contre :
Bloc de code:
int fact(int n, int acc) {
if(n <= 1) {
return acc;
}
return fact(n-1, n*acc);
}
Cette fonction est récursive terminale. Je ne crois pas qu'il y ait une méthode générale pour transformer une fonction récursive en une fonction récursive terminale, mais en principe une bonne piste est d'utiliser un ou plusieurs accumulateurs.
Je crois que certains (bon) compilateurs traitent les fonctions récursives terminales comme des fonctions itératives (pas de sauvegarde de contexte à chaque appel).
J'ai retrouvé l'un de mes TP de Caml de l'année dernière qui parlait de ça, peut-être que ça pourra t'aider. Sinon il doit certainement y avoir des infos sur Google.
http://laure.gonnord.org/pro/teaching/RICM-LP2/tp1-enonce.pdf
En tout cas en Caml c'est super important de savoir transformer des fonctions en récursives terminales, parce qu'on gagne vraiment en rapidité. Mais c'est très souvent bien plus dur à écrire, et on commence parfois par écrire la version non terminale avant de la transformer.
Quoi qu'il en soit, on est censé pouvoir réécrire n'importe quelle fonction récursive terminale en une fonction itérative assez facilement.
Je suis curieux de savoir comment le compilateur d'Objective C traite les fonctions récursives terminales. Je vais me renseigner un peu.
), j'ai vu un truc que j'avais jamais remarqué sur la version ObjC :
