12.5 Utiliser la récursivité pour résoudre des problèmes
Objectifs d'apprentissage
À la fin de cette section, vous devriez être capable de :
- Utiliser la récursivité pour effectuer une recherche efficace dans une liste.
- Démontrer une solution au problème des trois tours.
Recherche binaire
La recherche dans une liste triée implique généralement d'examiner chaque élément. Si l'élément recherché n'est pas trouvé, la recherche peut alors prendre beaucoup de temps.
La recherche binaire est un algorithme récursif utilisé pour effectuer une recherche efficace dans des listes triées. À chaque étape récursive, environ la moitié des éléments est éliminée car ne pouvant pas correspondre, ce qui permet à la recherche de progresser beaucoup plus rapidement.
Une recherche binaire commence par examiner l'élément central de la liste. Si la clé de recherche est trouvée, l'algorithme renvoie l'emplacement correspondant (cas de base). Sinon, la recherche est répétée sur environ la moitié de la liste. Si la clé est supérieure à l'élément central, elle doit alors se trouver dans la moitié droite, et inversement. Le processus se poursuit en vérifiant l'élément central de la moitié restante de la liste.
Exemple 12.3
Recherche binaire
""" Binary Search """
def binary_search(search_list, low, high, key):
# Check base case
if high > low:
mid = (high + low) // 2
# If element is present at the middle itself (base case)
if search_list[mid] == key:
return mid
# Recursive case: check which subarray must be checked
# Right subarray
elif key > search_list[mid]:
return binary_search(search_list, mid + 1, high, key)
# Left subarray
else:
return binary_search(search_list, low, mid - 1, key)
else:
# Key not found (other base case)
return "Not found"
# Test list
in_list = [1, 3, 13, 16, 19, 22, 27, 32, 48, 66, 78, 99, 111, 122]
# Call binary search function
print(binary_search(in_list, 0, len(in_list)-1, 48)) # Key exists at index 8
print(binary_search(in_list, 0, len(in_list)-1, 86)) # Key does not exist
La sortie du code ci-dessus est :
8
Not found
Concepts en pratique
Recherche binaire
Résoudre le problème des trois tours
Comme nous l'avons vu dans une section précédente, le problème des trois tours peut être résolu à l'aide de la récursivité. La solution repose sur deux appels à la solution du problème immédiatement plus petit. Comme le montre l'exemple de code ci-dessous, la solution récursive permet de résoudre le problème pour n'importe quel nombre d'anneaux.
Exemple 12.4
Résoudre N tours
La résolution du problème des trois tours est simple avec la récursivité. Dans le code ci-dessous, les anneaux sont numérotés de haut en bas. Le plus petit anneau est le 1, le suivant est le 2, et pour une résolution avec trois anneaux, l'anneau inférieur est le 3.
""" Solving the towers problem recursively """
def three_towers(N, source_tower, dest_tower, temp_tower):
# Base case: simply move the single(bottom) ring from source to destination tower
if N==1:
print("Move ring 1 from tower", source_tower, "to tower", dest_tower)
return # Exit when the base case is reached
# Recursive case
# Call the smaller version of the problem:
# to move the N-1 stack to the middle tower
three_towers(N-1, source_tower, temp_tower, dest_tower)
# Move the N ring to the destination tower
print("Move ring", N, "from tower", source_tower, "to tower", dest_tower)
# Call the smaller version of the problem:
# to now move the N-1 stack from the middle tower
# to the destination
three_towers(N-1, temp_tower, dest_tower, source_tower)
# Test code
print("Solution for 3 rings:")
three_towers(3, 't1', 't3', 't2') # t1, t2, t3 are the towers
La sortie du code ci-dessus est :
Solution for 3 rings:
Move ring 1 from tower t1 to tower t3
Move ring 2 from tower t1 to tower t2
Move ring 1 from tower t3 to tower t2
Move ring 3 from tower t1 to tower t3
Move ring 1 from tower t2 to tower t1
Move ring 2 from tower t2 to tower t3
Move ring 1 from tower t1 to tower t3
Concepts en pratique
Résoudre le problème des trois tours
À vous d'essayer
Combinaisons de pièces
Écrivez une fonction récursive print_H_T() qui produit toutes les combinaisons possibles de face ("H") et pile ("T") pour un nombre donné de lancers de pièce.
Ex. : Pour trois pièces, le programme doit afficher la sortie ci-dessous.
HHH
HHT
HTH
HTT
THH
THT
TTH
TTT