Chapitre 4 : Récursivité.

3. Exercice : Fonction factorielle

La fonction factorielle est définie par : \( n!=n \times (n-1) \times (n-2) \times... \times 2 \times 1 \)

1. Programmer la fonction facto_recur(n) de manière récursive.
2. Programmer la fonction facto_itera(n) de manière itérative.

4. Exercice : La suite de Fibonacci

La suite de Fibonacci est définie ainsi :

Les deux premiers termes sont égaux à 1 et chaque terme suivant est la somme des deux termes précédents.

Considérons la fonction fibo (que nous programmerons plus loin) qui à un nombre n renvoie n terme de la suite de Fibonacci :

• fibo(1) renvoie 1
• fibo(2) renvoie 1
• fibo(3) renvoie 2
• fibo(4) renvoie 3
• etc.

Ainsi :

1. Programmer la fonction fibo_recur(n) de manière récursive.
2. Programmer la fonction fibo_itera(n) de manière itérative.

5. Exercice

1. Programmer la fonction compte_voyelle_recur qui prend comme paramètre un string texte et qui retourne un integer correspondant au nombre de voyelles. La progammation doit être récursive.
2. Programmer la fonction compte_voyelle_itera qui prend comme paramètre un string texte et qui retourne un integer correspondant au nombre de voyelles. La progammation doit être itérative.

6. Exercice : pleins de lapins

On considère des lapins ayant les propriétés suivantes:

• Au départ, il y a un seul couple de lapins adultes.
• Chaque mois:
  • chaque couple de lapins adultes du mois précédents a donné naissance à un couple de bébés.
  • chaque couple de lapins bébés du mois précédents a grandi et est devenu un couple d'adolescents.
  • chaque couple de lapins adolescents du mois précédents a grandi et est devenu un couple de lapins adultes.
• On les considère immortels.

Ce qui nous donne :

Mois	0	1	2	3	4	5	6
	adultes=2 adolescents=0 bébés=0	adultes=2 adolescents=0 bébés=2	adultes=2 adolescents=2 bébés=2	adultes=4 adolescents=2 bébés=2	adultes=6 adolescents=2 bébés=4	adultes=8 adolescents=4 bébés=6	adultes=12 adolescents=6 bébés=8

1. Programmer la fonction lapin_recur qui retourne le nombre de lapins en fonction du mois. La progammation doit être récursive.
2. Programmer la fonction lapin_itera qui retourne le nombre de lapins en fonction du mois. La progammation doit être itérative.

7. Exercice

En mathématiques, on considère les coefficients binomiaux \(\begin{pmatrix} n\\p\end{pmatrix}\) avec \(n\) et \(p\) appartenant à \(\mathbb{N}\), \(1 \leq n\) et \(0 \leq p \leq n\).

Nous pouvons les construire de deux façons:

• Par récurrence :
  • \(\begin{pmatrix} 1\\0\end{pmatrix}=1\) et \(\begin{pmatrix} 1\\1\end{pmatrix}=1\)
  • \(\begin{pmatrix} n\\0\end{pmatrix}=1\) pour tout \(n\) appartenant à \(\mathbb{N}\) et \(n>0\)
  • \(\begin{pmatrix} n\\n\end{pmatrix}=1\) pour tout \(n\) appartenant à \(\mathbb{N}\) et \(n>0\)
  • \(\begin{pmatrix} n\\p\end{pmatrix}=\begin{pmatrix} n-1\\p-1\end{pmatrix} + \begin{pmatrix} n-1\\p\end{pmatrix}\)
• Par itération :

  Nous possédons la formule suivante : \(\begin{pmatrix} n\\p\end{pmatrix}=\frac{n!}{p!(n-p)!}\)

Ainsi:

1. Construire la fonction coeff_binom_recur(n,p) grâce aux conditions de récurrence.
2. Construire la fonction coeff_binom_itera(n,p) grâce à la dernière formule.

8. Exercice : (sujet 7 -2023)

Le but de cet exercice est d’écrire une fonction récursive traduire_romain qui prend en paramètre une chaîne de caractères, non vide, représentant un nombre écrit en chiffres romains et qui renvoie son écriture décimale.

Les chiffres romains considérés sont : I, V, X, L, C, D et M. Ils représentent respectivement les nombres 1, 5, 10, 50, 100, 500, et 1000 en base dix.

On dispose d’un dictionnaire romains dont les clés sont les caractères apparaissant dans l’écriture en chiffres romains et les valeurs sont les nombres entiers associés en écriture décimale :

romains = {"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000}

Le code de la fonction traduire_romain fournie repose sur le principe suivant :

• la valeur d’un caractère est ajoutée à la valeur du reste de la chaîne si ce caractère a une valeur supérieure (ou égale) à celle du caractère qui le suit ;
• la valeur d’un caractère est retranchée à la valeur du reste de la chaîne si ce caractère a une valeur strictement inférieure à celle du caractère qui le suit.

Ainsi, XIV correspond au nombre 10 + 5 - 1 puisque :

• a valeur de X (10) est supérieure à celle de I (1), on ajoute donc 10 à la valeur du reste de la chaîne, c’est-à-dire IV ;
• la valeur de I (1) est strictement inférieure à celle de V (5), on soustrait donc 1 à la valeur du reste de la chaîne, c’est-à-dire V.

On rappelle que pour priver une chaîne de caractères de son premier caractère, on utilisera l’instruction :

nom_de_variable[1:]

Par exemple, si la variable mot contient la chaîne "CDI", mot[1:] renvoie "DI".

Compléter le code de la fonction traduire_romain et le tester.

def traduire_romain(nombre):
    """ Renvoie l’écriture décimale du nombre donné en chiffres
    romains """
    if len(nombre) == 1:
        return ...
    elif romains[nombre[0]] >= ...
        return romains[nombre[0]] + ...
    else:
        return ...

Exemples :

>>> traduire_romain("XIV")
14
>>>traduire_romain("CXLII")
142
>>> traduire_romain("MMXXIII")
2023

9. Exercice : (sujet 23 - 2023)

On considère des tableaux de nombres dont tous les éléments sont présents exactement trois fois à la suite, sauf un élément qui est présent une unique fois et que l'on appelle « l'intrus ». Voici quelques exemples :

tab_a = [3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5]
#l'intrus est 7
tab_b = [8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3]
#l'intrus est 8
tab_c = [5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8]
#l'intrus est 3

On remarque qu'avec de tels tableaux :

• pour les indices multiples de 3 situés strictement avant l'intrus, l'élément correspondant et son voisin de droite sont égaux,
• pour les indices multiples de 3 situés après l'intrus, l'élément correspondant et son voisin de droite - s'il existe - sont différents.

Ce que l'on peut observer ci-dessous en observant les valeurs des paires de voisins marquées par des caractères ^ :

[3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5]
 ^  ^     ^  ^     ^  ^     ^  ^     ^  ^     ^  ^     ^  ^     ^
 0        3        6        9        12       15       18       21

Dans des listes comme celles ci-dessus, un algorithme récursif pour trouver l'intrus consiste alors à choisir un indice i multiple de 3 situé approximativement au milieu des indices parmi lesquels se trouve l'intrus.

Puis, en fonction des valeurs de l'élément d'indice i et de son voisin de droite, à appliquer récursivement l'algorithme à la moitié droite ou à la moitié gauche des indices parmi lesquels se trouve l'intrus.

Par exemple, si on s’intéresse à l’indice 12, on voit les valeurs 2 et 4 qui sont différentes : l’intrus est donc à gauche de l’indice 12 (indice 12 compris).

En revanche, si on s’intéresse à l’indice 3, on voit les valeurs 9 et 9 qui sont identiques : l’intrus est donc à droite des indices 3-4-5, donc à partir de l’indice 6.

Compléter la fonction récursive trouver_intrus qui met en œuvre cet algorithme.

tab_a = [3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5]

tab_b = [8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3]

tab_c = [5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8]

def trouver_intrus(tab, g, d):
    '''
    Renvoie la valeur de l'intrus situe entre les indices g et d
    dans la liste tab ou :
        tab verifie les conditions de l'exercice,
        g et d sont des multiples de 3.
    '''
    if g == d:
        return ...

    else:
        nombre_de_triplets = (d - g)// ...
        indice = g + 3 * (nombre_de_triplets // 2)
        if ... :
            return ...
        else:
            return ...

Exemples :

>>> trouver_intrus([3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5], 0, 21)
7
>>> trouver_intrus([8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3],0, 12)
8
>>> trouver_intrus([5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8], 0, 15)
3