23 - 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 programme ci-dessous propose une fonction récursive compter_voyelles() permettant de compter les voyelles contenues dans un string. Le principe est simple : on commence par en faire l'appel sur l'indice 0 et elle répond
- si le caractère actuel n'est pas une voyelle 0 + la réponse que va lui fournir un nouvel appel sur l'indice suivant
- si le caractère actuel est bien une voyelle : 1 + la réponse que va lui fournir un nouvel appel sur l'indice suivant
Après avoir lu, lancé et compris le programme, dire
- sur quelles lignes se trouvent la condition d'arrêt et le cas de base correspondant ?
- sur quelles lignes se trouvent le cas récursif ?
1
2
3
4
5
6
7
8
9
10
11 |
|
02° Etudier la fonction récursive est_trie() qui renvoie True si le tableau d'entiers est trié en ordre croissant, False sinon.
Le principe est de commencer par regarder si t[0] est bien plus petit que t[1] et de continuer en comparant t[1] et t[2] ect... Dès qu'on détecte une anomalie, on peut répondre que c'est faux.
Après avoir lu, lancé et compris le programme, dire
- pourquoi on peut répondre True lorsqu'on arrive sur le dernier nombre et que tous les autres sont bien triés avant luip ?
- sur quelles lignes se trouve ce cas de base "je suis arrivé à la fin" ?
- sur quelles lignes se trouve l'autre cas de base : "j'ai détecté une erreur de rangement" ?
- sur quelles lignes se trouve le cas récursif : "répond ce qu'on va te dire l'appel sur l'indice suivant" ?
1
2
3
4
5
6
7
8
9
10
11 |
|
2 - Empilement
03° Fournir (sous la forme proposée ci-dessous) 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
9 |
|
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
Nous allons travailler avec une fonction récursive travaillant sur de la concaténation de tableaux. Revoyons d'abord comment fonctionne cette concaténation sur les tableaux : l'opérateur + possède une signature comportant des lists Python qui signifie concaténation, comme lorsqu'on l'utilise avec le type str :
Signature possible du symbole + : list + list -> list
Exemple :[5, 10] + [20, 10] -> [5, 10, 20, 10]
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'une liste non-homogène.
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 |
|
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.