Leçon 15 : Récursion, backtracking et introduction à la programmation dynamique
Tu es arrivé/e à la leçon de synthèse — bravo ! Commençons avec une poupée matriochka : une poupée qui contient une plus petite poupée, jusqu'à la toute petite qui ne s'ouvre plus. C'est exactement la « récursion » : une fonction qui s'appelle elle-même sur une version plus petite du même problème,
La récursion, c'est comme une poupée russe : chaque poupée en ouvre une plus petite, jusqu'à atteindre la toute petite qui ne s'ouvre pas (le cas de base). Le backtracking, c'est essayer un chemin, et si c'est une impasse — le refermer et en essayer un autre. La memoization, c'est noter sur un papier les réponses déjà calculées, pour ne pas les recalculer.
- récursion et backtracking
- Récursion : une fonction qui s'appelle elle-même sur un sous-problème plus petit jusqu'à un cas de base. Backtracking : essayer un choix, faire une récursion, et annuler le choix pour explorer toutes les possibilités.
- cas de base
- La condition qui arrête la récursion et renvoie une réponse directe sans appel supplémentaire — sans elle, la récursion ne se termine jamais.
- memoization (mémorisation des résultats)
- Mettre en cache les résultats des sous-problèmes (par exemple dans un dict) pour ne pas les recalculer — cela évite le travail répété et peut considérablement accélérer l'exécution (par exemple, Fibonacci naïf passe de O(2ⁿ) à O(n)).
