Récursivité et retour arrière
Les fondamentaux de la récursivité
Une fonction récursive s'appelle elle-même avec une version plus petite du problème jusqu'à atteindre un cas de base qui arrête la chaîne.
Toute récursion a besoin de deux choses :
- Cas de base - l'entrée la plus simple où l'on retourne directement.
- Cas récursif - décomposer le problème et s'appeler soi-même.
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
La pile d'appels - Visualisée
Chaque appel récursif empile un cadre (frame) sur la pile d'appels. Quand le cas de base retourne, les cadres se dépilent en ordre inverse.
factorial(4)
→ factorial(3)
→ factorial(2)
→ factorial(1) → returns 1
← returns 2
← returns 6
← returns 24
Sans cas de base, la pile déborde. La limite de récursion par défaut de Python est de 1 000 frames.
Fibonacci - Le piège classique
Le Fibonacci récursif naïf est en O(2ⁿ) car il recalcule les mêmes sous-problèmes. La mémoïsation corrige cela en O(n) en temps et en espace.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
Backtracking - Tout essayer, puis défaire
Le retour sur trace (backtracking) est la récursivité avec une astuce : on fait un choix, on recurse, puis on annule le choix avant d'essayer l'option suivante. Comme explorer un labyrinthe - avancer, atteindre un cul-de-sac, revenir en arrière, essayer un autre chemin.
Le template de backtracking
def backtrack(state, choices):
if is_solution(state):
result.append(state.copy())
return
for choice in choices:
if is_valid(choice):
state.add(choice) # choose
backtrack(state, ...) # explore
state.remove(choice) # un-choose
Ce patron en trois étapes - - est la colonne vertébrale de presque tout problème de backtracking.
Discussion
Sign in to join the discussion