[ALGO] Récursivité terminale... Fermé

Question

Bonjour,
Je souhaiterai ce qu'est une fonction récursive non terminale et terminale, et quel est la différence entre ces deux récursivités.
Merci

ekra · Accepted Answer

Bonjour,

Une fonction récursive terminale n'effectue pas d'autre opération qu'un dépilement après l'apelle récursif ou le test d'arret de la récursivité. Une fonction récursive non terminale fabrique son résultat au dépilement des fonctions.
Lors d'une récursivité terminale, il est inutile de sauver le contexte de la fonction. Si le compilateur peut optimiser, on gagne en espace mémoire et en temps d'execution.

Exemple :
(Language C)

Factorielle non terminale :

int factorielle(int n) {
  if (n <= 1) { return 1; }
  return n * factorielle(n - 1);
}


Factorielle terminale

#define factorielle(n) (factorielle(n , 1))

int factorielle(int n, int resultat) {
  if (n <= 1) { return resultat; }
  return factorielle(n-1, n * resultat);
}

[ALGO] Récursivité terminale...

1 réponse

Discussions similaires