Chapitre 4 : Récursivité.

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

Par définition, \( 0! = 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.

Exemples :

>>> facto_recur(5)
120
>>> facto_recur(0)
1
>>> facto_itera(5)
120

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.

On définit la fonction fibo telle que :

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

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

1. Programmer la fonction compte_voyelle_recur(texte) qui retourne le nombre de voyelles dans texte (version récursive).
2. Programmer la fonction compte_voyelle_itera(texte) qui retourne le nombre de voyelles dans texte (version itérative).

On considère les voyelles : a, e, i, o, u, y (minuscules et majuscules).

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

• Au départ, il y a un seul couple de lapins adultes (soit 2 lapins).
• Chaque mois :
  • chaque couple de lapins adultes du mois précédent donne naissance à un couple de bébés,
  • chaque couple de bébés devient adolescent,
  • chaque couple d’adolescents devient adulte.
• On les considère immortels.

Exemple d’évolution (nombre de lapins adultes, adolescents et bébés) :

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.

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.

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.

Exemples :

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

Une utilisation "classique" de « diviser pour régner » est son utilisation sur les listes et avec une récurrence.

Soit tab un tableau non vide d'entiers triés dans l'ordre croissant et n un entier.

La fonction chercher ci-dessous doit renvoyer un indice où la valeur n apparaît dans tab si cette valeur y figure et None sinon.

Les paramètres de la fonction sont :

• tab, le tableau dans lequel s'effectue la recherche
• n, l'entier à chercher dans le tableau
• i, l'indice de début de la partie du tableau où s'effectue la recherche
• j, l'indice de fin de la partie du tableau où s'effectue la recherche

L’algorithme demandé est une recherche dichotomique récursive.

Exemples :

>>> chercher([1, 5, 6, 6, 9, 12], 7, 0, 10)
>>> chercher([1, 5, 6, 6, 9, 12], 7, 0, 5)
>>> chercher([1, 5, 6, 6, 9, 12], 9, 0, 5)
4
>>> chercher([1, 5, 6, 6, 9, 12], 6, 0, 5)
2

On s’intéresse à un algorithme récursif qui permet de rendre la monnaie à partir d’une liste donnée de valeurs de pièces et de billets.

Le système monétaire est : [100, 50, 20, 10, 5, 2, 1] (disponibles en quantité illimitée).

On cherche à donner la liste des valeurs à rendre pour une somme donnée a_rendre, en partant d’un indice rang dans cette liste (glouton : on prend la plus grande valeur possible à partir de rang).

Compléter la fonction rendu_glouton(a_rendre, rang) récursive.

Exemples attendus :

>>> rendu_glouton(67, 0)
[50, 10, 5, 2]
>>> rendu_glouton(291, 0)
[100, 100, 50, 20, 20, 1]
>>> rendu_glouton(291, 1)  # sans billets de 100
[50, 50, 50, 50, 50, 20, 20, 1]

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.

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