Structures de données et algorithmes · Fondamentaux

Récursivité

Une fonction qui résout un problème en s'appelant elle-même sur une version plus petite du même problème.

Commencer une leçon sur Récursivité

À apprendre d'abord

• Analyse de complexité: Décrire comment le temps d'exécution ou la mémoire d'un algorithme croît avec la taille des données, en utilisant le grand O.

Mène à

• Tris diviser-pour-régner: Les tris diviser-pour-régner, tri fusion et tri rapide, qui battent le O(n carré) en découpant le problème.
• Arbres binaires: Une structure hiérarchique où chaque nœud a au plus deux enfants.
• Retour sur trace (backtracking): Essayer un choix, récurer, puis l'annuler s'il ne mène nulle part, pour explorer toutes les possibilités.

Notions liées

• Diviser pour régner: Découper un problème en copies indépendantes plus petites de lui-même, résoudre chacune, puis combiner.
• Retour sur trace (backtracking): Essayer un choix, récurer, puis l'annuler s'il ne mène nulle part, pour explorer toutes les possibilités.