Exo Recursivité

Identification

Infoforall

16 - Exos Récursivité


Attention, le soin est noté et les codes markdown identiques seront sanctionnés à moins de noter clairement que vous avez travaillé avec un autre élève de la classe.

1 - Vocabulaire

01° Le code ci-dessous propose une classe Cellule permettant de réaliser au besoin une liste chaînée. On fournit également une fonction récursive derniere qui permet de trouver la dernière cellule de la liste.

Après avoir lu, lancé et compris ce bout de code, dire

  1. sur quelle ligne se trouve la condition d'arrêt
  2. sur quelle ligne se trouve le cas de base
  3. sur quelle ligne se trouve le cas récursif
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
class Cellule : def __init__(self, valeur, suivant=None) : self.valeur = valeur self.suivant = suivant def derniere(cellule) : if cellule.suivant == None : return cellule else : return derniere(cellule.suivant) if __name__ == "__main__" : c3 = Cellule("Dernier") c2 = Cellule("Avant dernier", c3) c1 = Cellule("Premier", c2) print(derniere(c1).valeur)

02° Réaliser la fonction récursive compter qui compte le nombre de cellules dans la chaîne.

Sa condition d'arrêt est que la cellule étudiée n'ai pas de successeur.

Dans ce cas, le cas de base est de renvoyer 1.

Le cas récursif consiste à renvoyer 1 + compter(cellule.suvant)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
class Cellule : def __init__(self, valeur, suivant=None) : self.valeur = valeur self.suivant = suivant def derniere(cellule) : if cellule.suivant == None : return cellule else : return derniere(cellule.suivant) def compter(cellule) : pass if __name__ == "__main__" : c3 = Cellule("Dernier") c2 = Cellule("Avant dernier", c3) c1 = Cellule("Premier", c2) print(compter(c1))

Vous devriez afficher 3 dans la console Python avec le programme-exemple.

2 - Empilement

03° Fournir (sous la forme proposée) l'empilement provoqué par la fonction récursive recherche jusqu'au cas de base lorsqu'on lance l'appel recherche("aAaA", "A"). Pensez à décaler votre réponse de 4 espaces sur le markdown pour qu'il utilise bien une police à chasse fixe.

1 2 3 4 5 6 7 8
def recherche(texte, caractere, indice=0) : if indice == len(texte) : # condition d'arrêt return 0 # cas de basee else : if caractere == texte[indice] : return 1 + recherche(texte, caractere, indice+1) else : return recherche(texte, caractere, indice+1)

Exemples d'utilisation :

>>> recherche("AAAaaaA", "A") 4 >>> recherche("AAAaaaA", "a") 3

Début de la réponse :

Appel à recherche("aAaA", "A") va renvoyer recherche("aAaA", "A", 1) Appel à recherche("aAaA", "A", 1) va renvoyer 1 + ...

3 - Dépilement

On travaille avec la fonction récursive suivante, qui propose de créer un tableau par concaténation successive.

04° Que contient le tableau tab à la suite des instructions suivantes :

>>> tab = [] >>> tab = [5] + tab >>> tab [5] >>> tab = tab + [10] >>> tab [5, 10] >>> tab = [15] + tab >>> tab ???

Voici maintenant une fonction récursive qui crée un tableau contenant les types des données stockées dans chaque case d'un tableau non-homogène initial.

Exemple d'utilisation :

>>> tab = [5, "5", (5,), [5]] >>> donne_type(tab) [<class 'int'>, <class 'str'>, <class 'tuple'>, <class 'list'>]

Pour information, voici le code de la fonction. Vous n'aurez pas à l'utiliser dans le cadre de cet exercice. Je donne également une version non récursive qui fait exactement la même chose.

1 2 3 4 5 6 7 8 9 10 11
# Version non récursive def donne_type2(tableau) : return [type(valeur) for valeur in tableau] # Version récursive def donne_type(tableau, index=0) : if index == len(tableau) : return [] else : contenu = type(tableau[index]) return [contenu] + donne_type(tableau, index+1)

05° Donner le résultat qui va fournir l'appel initial à partir de l'empilement suivant. A vous de dépiler progressivement.

Appel à donne_type(tableau) va renvoyer [<class 'str'>] + donne_type(tableau, 1) Appel à donne_type(tableau, 1) va renvoyer [<class 'int'>] + donne_type(tableau, 2) Appel à donne_type(tableau, 2) va renvoyer [<class 'int'>] + donne_type(tableau, 3) Appel à donne_type(tableau, 3) renvoie []

Activité publiée le 21 10 2020
Dernière modification : 21 10 2020
Auteur : ows. h.