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

Récursivité — définition ?

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

Fonction récursive — rôle ?

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

Cas de base — importance ?

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

Appel récursif — mécanisme ?

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

Pile d’exécution — fonction ?

Structure stockant les états des appels en cours.

Profondeur maximale — limite ?

Nombre maximal d’appels récursifs avant erreur.

RecursionError — cause ?

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

Appels redondants — problème ?

Recalculs inutiles, inefficaces en performance.

Coût des appels — impact ?

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

Puissance — relation récursive ?

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

Factorielle — définition ?

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

Tour de Hanoï — principe ?

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

Fibonacci récursif — inconvénient ?

Exponentialité du temps à cause des appels redondants.

Fibonacci itératif — avantage ?

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

Multiplication russe — principe ?

Division par 2, doublement, addition conditionnelle.

Calcul factorielle — méthode efficace ?

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