22 - Exos Récursivité

⏪

⏬

⏩

1 - Vocabulaire

2 - Empilement

3 - Dépilement

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 ?

def compter_voyelles(s:str, i:int) -> int:
    '''Renvoie le nombre de voyelles détéctées dans le string s à partir de l'indice i et plus'''
    if i >= len(s):
        return 0
    else:
        nb = 0
        if s[i] in "AaEeYyUuIiOo":
            nb = 1
        return nb + compter_voyelles(s, i+1)
 
print(compter_voyelles("Bonjour", 0))

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" ?

def est_trie(t:list, i:int) -> bool:
    '''Renvoie True si le tableau de nombres est trié à partir de t[i], False sinon'''
    if i == len(t) - 1:
        return True
    elif t[i] > t[i+1]:
        return False
    else:
        return est_trie(t, i+1)
 
print(est_trie([5, 10, 20, 30], 0))
print(est_trie([5, 10, 40, 30], 0))

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.

def recherche(texte:str, caractere:str, i:int=0) -> int:
    '''Renvoie le nombre de fois où caractère est présent dans texte à partir de l'indice i'''
    if i == len(texte):  # condition d'arrêt
        return 0         # cas de basee
    else:
        if caractere == texte[i]:
            return 1 + recherche(texte, caractere, i+1)
        else:
            return recherche(texte, caractere, i+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

⇩ ⇧ ⤊

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.

# Version non récursive utilisant une création par compréhension
def donne_type2(t):
    return [type(v) for v in t]
 
# Version récursive
def donne_type(t, i=0):
    if i == len(t):
        return []
    else:
        contenu = type(t[i])
        return [contenu] + donne_type(t, i+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.

⏪

⏫

⏩