Flashcards : Maîtrise des algorithmes récursifs essentiels — 16 cartes

Méthode où une fonction s’appelle elle-même pour résoudre un problème.

Elle s’appelle elle-même pour traiter un problème en le décomposant.

Il arrête la récursion pour éviter une boucle infinie.

Une fonction s’invoque avec des paramètres modifiés.

Structure stockant les états des appels en cours.

Nombre maximal d’appels récursifs avant erreur.

Dépassement de la limite de profondeur d’appel.

Recalculs inutiles, inefficaces en performance.

Consomme temps et mémoire, peut être coûteux.

x^n = x * x^(n-1), avec n=0 comme base.

Produit de tous les entiers de 1 à n, 0!=1.

Déplacer n disques en décomposant en sous-problèmes.

Exponentialité du temps à cause des appels redondants.

Calcul en temps linéaire, utilisation mémoire minimale.

Division par 2, doublement, addition conditionnelle.

Itérative généralement plus performante que récursive.