29 - 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.

MODE COURS (cacher les questions)

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

0 + la réponse que va lui fournir un nouvel appel sur l'indice suivant si le caractère actuel n'est pas une voyelle.
1 + la réponse que va lui fournir un nouvel appel sur l'indice suivant si le caractère actuel est bien une voyelle.

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.

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))

Après avoir lu, lancé et compris le programme, répondre à ces questions :

Pourquoi répondre True lorsqu'on arrive sur le dernier nombre et que tous les autres sont bien triés avant lui ?
Sur quelles lignes se trouve ce cas de base "je suis arrivé à la fin" ?
Sur quelles lignes se trouve le 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" ?

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').

Cette fonction renvoie le nombre d'occurrences du caractère cherché (le nombre de fois où le caractère cherché est présent).

Si vous redigez en Markdown, pensez à décaler votre réponse de 4 espaces pour que l'interpréteur Markdown utilise bien une police à chasse fixe.

def recherche(texte:str, caractere:str, i:int=0) -> int:
    """Renvoie le nombre d'occurrences du caractère sur les indices i et plus"""
     
    if i == len(texte):  # cas de base et condition d'arrêt
        return 0
    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 compatible avec le type list-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
???
 
>>> tab = tab + [90]
>>> tab
???

Voici maintenant une fonction récursive qui reçoit un tableau potentiellement non-homogène et renvoie un tableau de strings où chaque case contient le type de données de la case correspondante dans le tableau d'entrée.

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 cette fonction.

def donne_type(t:list, i:int=0) -> list:
    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 ['str'] + donne_type(tableau, 1)
    Appel à donne_type(tableau, 1) va renvoyer ['int'] + donne_type(tableau, 2)
        Appel à donne_type(tableau, 2) va renvoyer ['int'] + donne_type(tableau, 3)
            Appel à donne_type(tableau, 3) renvoie []

Pour informations, voici une version plus courte de la même fonction réalisée en utilisant simplement la création par compréhension vue en 1er.

 1
 2
 3

# Version non récursive utilisant une création par compréhension
def donne_type2(t):
    return [type(v) for v in t]

FIN

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

⏪

⏫

⏩