Les exemples de récursions présentés ici ont une forme non terminale. Ils ne peuvent être convertis en structure itérative sans utiliser de pile (DEPS / LIFO).
from typing import List
import os
def listerDossierRec(dossier: str) -> List[str]:
"""
liste récursivement le contenu d'un dossier
@param dossier le chemin vers le dossier à lister
@return le contenu du dossier et de ces sous-dossiers
précondition : dossier existe
"""
assert os.path.isdir(dossier) #vérification de la pré-condition
contenu = []
for element in os.listdir(dossier):
chemin = os.path.join(dossier, element) #"join(/home/etu", "Cours") -> /home/etu/Cours"
if os.path.isdir(chemin):
contenu.append(chemin)
contenu.extend(listerDossierRec(chemin))
return contenu
Essayer et faire la trace de cette fonction.
La commande find permet (entre autres) de rechercher un fichier dans un
dossier ; en voici une version Python :
from typing import List
import os
def rechercherLesFichiers(dossier: str, rech: str) -> List[str]:
"""
recherche les fichiers d'un dossier
@param dossier le chemin vers le dossier à scruter
@param rech le critère de recherche (sous-chaîne d'un nom de fichier)
@return le chemin des fichiers trouvés
précondition : dossier existe
"""
assert os.path.isdir(dossier) #vérification de la pré-condition
trouve = []
for element in os.listdir(dossier):
chemin = os.path.join(dossier, element)
if rech in element: #si le nom du fichier contien rech
trouve.append(chemin)
if os.path.isdir(chemin):
trouve.extend(rechercherLesFichiers(chemin, rech))
return trouve
Essayer et faire la trace de cette fonction.
- (Expliquer la différence entre extend et append.)
Une variante de l’exemple précédent qui renvoie uniquement le premier fichier trouvé, et qui n’inspecte les sous-dossiers que si c’est nécessaire :
from typing import List, Optional
import os
def rechercherUnFichier(dossier: str, rech: str) -> Optional[str]:
"""
recherche un fichier
@param dossier le chemin vers le dossier à scruter
@param rech le critère de recherche (sous-chaîne d'un nom de fichier)
@return le chemin du premier fichier trouvé
précondition : dossier existe
"""
result = None
contenu = os.listdir(dossier)
sousDossiers = []
i = 0
while result == None and i < len(contenu):
chemin = os.path.join(dossier, contenu[i])
if rech.lower() in contenu[i].lower():
result = chemin
elif os.path.isdir(chemin):
sousDossiers.append(chemin) #on mémorise le sous-dossier pour la recherche récursive
i += 1
if result == None: #non trouvé dans le dossier courant
i = 0
while result == None and i < len(sousDossiers):
result = rechercherUnFichier(sousDossiers[i], rech)
i += 1
return result
- Essayer et faire la trace de cette fonction et comparer son fonctionnement
à la précédente (
rechercherLesFichiers). - (Expliquer le type
Optional.)
Cet exemple reprend le parcours d’un dossier, mais dans une version itérative (en utilisant une pile DEPS / LIFO) — implémentée sous la forme d’un tableau :
from typing import List
import os
def listerDossierIte(dossier: str) -> str:
assert os.path.isdir(dossier)
dossiers = [dossier] #pile LIFO
contenu = []
while len(dossiers) != 0: #tant que la pile n'est pas vide
#tant qu'il reste des dossiers à traiter
dossier = dossiers.pop() #dépiler (enlève et renvoie le dernier)
for element in os.listdir(dossier):
chemin = os.path.join(dossier, element)
contenu.append(chemin)
if os.path.isdir(chemin):
dossiers.append(chemin) #empiler le dossier à traiter (ultérieurement)
return contenu
- Essayer et faire la trace de cette fonction et comparer son fonctionnement
à la version récursive (
listerDossierRec).