Récursivité - Correction des exercices

    Compléments

    La fonction somme(n) du cours

Une fois que l’on dispose d’une définition récursive pour une fonction, il est en général assez facile de la programmer en Python.

Il faut néanmoins faire attention à deux points importants :

  • Le domaine mathématique d’une fonction, c’est-à dire les valeurs sur lesquelles elle est définie, n’est pas toujours le même que l’ensemble des valeurs du type Python avec lesquelles elle sera appelée.
  • Le choix d’une définition récursive plutôt qu’une autre peut dépendre du modèle d’exécution des fonctions récursives, en particulier quand il s’agit de prendre en compte des contraintes d’efficacité.

Exemple

Le code de la fonction somme(n) rappelé ci-dessous,ne se comporte pas exactement comme la fonction mathématique.

In [1]:
def somme(n):
        if n == 0:
            return 0
        else:
            return n + somme(n - 1)
In [2]:
somme(5)
Out[2]:
15

La principale différence est que la fonction mathématique est uniquement définie pour des entiers naturels,
alors que la fonction somme(n) peut être appelée avec un entier Python arbitraire, qui peut être une valeur négative.

Bien que la fonction mathématique ne soit pas définie pour n = −1, l’appel somme(-1) ne provoque aucune erreur immédiate,
mais il implique un appel à somme(-2), qui déclenche un appel à somme(-3), etc.
Ce processus infini va finir par provoquer une erreur à l’exécution. </ul>

In [3]:
somme(-1)

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-3-2263d90c8da2> in <module>
----> 1 somme(-1)

<ipython-input-1-827459216c01> in somme(n)
      3             return 0
      4         else:
----> 5             return n + somme(n - 1)

... last 1 frames repeated, from the frame below ...

<ipython-input-1-827459216c01> in somme(n)
      3             return 0
      4         else:
----> 5             return n + somme(n - 1)

RecursionError: maximum recursion depth exceeded in comparison

Pour éviter ce comportement, c'est de restreindre les appels à la fonction somme(n) aux entiers positifs ou nuls.
Pour cela, on peut utiliser une instruction assert comme ci-dessous :

In [1]:
def somme(n):
    assert n >= 0 and type(n) == int , "entrer un entier naturel"
    if n == 0:
        return 0
    else:
        return n + somme(n - 1)
In [2]:
somme(5)
Out[2]:
15
In [3]:
somme(-1)

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-3-2263d90c8da2> in <module>
----> 1 somme(-1)

<ipython-input-1-03fb6a4a14f8> in somme(n)
      1 def somme(n):
----> 2     assert n >= 0 and type(n) == int , "entrer un entier naturel"
      3     if n == 0:
      4         return 0
      5     else:

AssertionError: entrer un entier naturel
In [4]:
somme(3.8)

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-4-70d0b2fdffc9> in <module>
----> 1 somme(3.8)

<ipython-input-1-03fb6a4a14f8> in somme(n)
      1 def somme(n):
----> 2     assert n >= 0 and type(n) == int , "entrer un entier naturel"
      3     if n == 0:
      4         return 0
      5     else:

AssertionError: entrer un entier naturel

Bien que cette solution soit correcte, elle n’est pas encore complètement satisfaisante.

En effet, pour tout appel somme(n) avec n >= 0, chaque appel récursif commencera par faire le test associé à l’instruction assert,
alors que chaque valeur de n, par la suite, sera nécessairement positive.

Une solution pour éviter ces tests inutiles est de définir deux fonctions :

    La première, somme_bis(n), implémente la définition récursive de la fonction mathématique somme(n) sans **vérifier son argument**.
In [ ]:
In [6]:
def somme_bis(n):
    if n == 0:
        return 0
    else:
        return n + somme_bis(n - 1)

La seconde, somme(n), est la fonction « principale » qui sera appelée par l’utilisateur.
Cette fonction ne fait que vérifier (une et une seule fois) que son argument n est positif puis, si c’est le cas, elle appelle la fonction somme_bis(n).

In [5]:
def somme(n):
    assert n >= 0 and type(n) == int , "entrer un entier naturel"
    return somme_bis(n)
In [7]:
somme(5)
Out[7]:
15
In [8]:
somme(-1)

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-8-2263d90c8da2> in <module>
----> 1 somme(-1)

<ipython-input-5-b44b2901aba8> in somme(n)
      1 def somme(n):
----> 2     assert n >= 0 and type(n) == int , "entrer un entier naturel"
      3     return somme_bis(n)

AssertionError: entrer un entier naturel

Conclusion



Un calcul peut être décrit à l’aide d’une définition récursive. L’avantage de cette technique est que l’implémentation est souvent plus proche de la définition. L’écriture d’une **fonction récursive** nécessite de distinguer les **cas de base**, pour lesquels on peut donner un résultat facilement, et les **cas récursifs**, qui font appel à la définition en cours. Il faut faire attention à ce que la fonction en Python ne s’applique que sur le **domaine** de la fonction mathématique, par exemple en utilisant l’instruction **assert**. Enfin, il faut comprendre le modèle d’exécution des fonctions récursives pour choisir la définition qui **limite le nombre d’appels récursifs**.

Correction des exercices

Exercice 1

Fonction Factorielle

  1. Fonction itérative
    a) En utilisant le boucle "for"
In [11]:
def fact_for(n):
    """
    Calcule la factorielle de n
    paramètre:
        n : (int) entier >= 0
    retour:
        un entier positif
    """
    assert k >= 0 and isinstance(k, int),"Vous devez entrer un entier positif"
    produit = 1
    for i in range(2, n+1):
        produit = produit * i
    return produit
In [12]:
fact_for(3)
Out[12]:
6

b) En utilisant le boucle "while"

In [13]:
def fact_while(n):
    """
    Calcule la factorielle de n
    paramètre:
        n : (int) entier >= 0
    retour:
        un entier positif
    """
    assert k >= 0 and isinstance(k, int),"Vous devez entrer un entier positif"
    produit = 1
    while n > 1:
        produit = produit * n
        n = n - 1
    return produit
In [14]:
fact_while(3)
Out[14]:
6
  1. Recopier et compléter :
    n! = n x (n-1) x ... x 1
    n! = n x (n-1)!

2) Fonction récursive

In [9]:
def fact_rec(n):
    """
    Calcule la factorielle de n
    paramètre:
        n : (int) entier >= 0
    retour:
        un entier positif
    """
    if n == 0:
        return 1
    else:
        return n * fact_rec(n - 1)
In [10]:
fact_rec(5)
Out[10]:
120

Exercice 2

Analyser un programme récursif
On considère la fonction mystere ci-dessous :

In [12]:
def mystere(liste):
    if len(liste) == 1:
        return liste[0]
    else:
        if liste[0] < liste[1]:
            liste.pop(1)
        else:
            liste.pop(0)
        return mystere(liste)
  1. Analyser ce programme, en déduire le rôle de cette fonction.
In [13]:
liste = [1, 5, -3, 4]
mystere(liste)
Out[13]:
-3
In [4]:
liste = [1, 5, 3, 4]
mystere(liste)
Out[4]:
1

Cette fonction retourne la plus petite valeur de la liste

  1. Donner une version itérative de cette fonction
In [6]:
def mystere_iter(liste):
    valeur = liste[0]
    for elt in liste:
        if elt < valeur:
            valeur = elt
    return valeur
In [7]:
liste = [1, 5, -3, 4]
mystere_iter(liste)
Out[7]:
-3
In [8]:
liste = [1, 5, 3, 4]
mystere_iter(liste)
Out[8]:
1

Exercice 3

Comprendre un programme récursif

  1. Compléter les égalités suivantes :

a x 0 = 0
a x b = a + a x (b - 1)

  1. Compléter le code de la fonction
In [15]:
def produit(a,b):
    if b == 0:
        return 0
    else:
        return a + produit(a, b-1)
In [17]:
produit(5, 3)
Out[17]:
15
In [11]:
produit(5, 2980)

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-11-4fdfe797142c> in <module>
----> 1 produit(5, 2980)

<ipython-input-9-f3069c2b8bd1> in produit(a, b)
      3         return 0
      4     else:
----> 5         return a + produit(a, b-1)

... last 1 frames repeated, from the frame below ...

<ipython-input-9-f3069c2b8bd1> in produit(a, b)
      3         return 0
      4     else:
----> 5         return a + produit(a, b-1)

RecursionError: maximum recursion depth exceeded in comparison
In [12]:
produit(10, 400)
Out[12]:
4000
  1. améliorer le code de cette fonction de façon à ce que le dépassement de pile de récursion n'arrive que lorsque a et b sont tous deux supérieurs à la taille maximale.
In [ ]:
def produit(a,b):
    if a > 2950 or b > 2950:
        return "a ou b dépassent le nombre d'appels recursif possible"
    if b == 0:
        return 0
    else:
        return a + produit(a, b-1)

Exercice 4

Additions et soustractions
On suppose qu'on ne dispose que de deux opérations : ajouter 1 ou retrancher 1.

  1. Écrire à l'aide de ces deux opérations, une version itérative de l'addition de deux entiers
In [18]:
# Avec une boucle while
def somme(a, b):
    """
    Calcule la somme de a et b
    paramètre:
        a : (int) entier 
        b : (int) entier 
    retour:
        un entier 
    """
    if b > 0:
        while b > 0:
            a = a + 1
            b = b - 1
    elif b < 0:
        while b < 0:
            a = a - 1
            b = b + 1
    return a

somme(-3, 5)
Out[18]:
2
In [19]:
# Avec une boucle for
def somme2(a, b):
    """
    Calcule la somme de a et b
    paramètre:
        a : (int) entier
        b : (int) entier
    retour:
        un entier 
    """

    if b > 0:
        for i in range(b):
            a = a + 1
    elif b < 0:
        for i in range(-b):
            a = a - 1
    return a

somme2(3, -5)
Out[19]:
-2
  1. Écrire à l'aide de ces deux opérations, une version récursive de l'addition de deux entiers
In [20]:
def somme_rec(a, b):
    """
    Calcule la somme de a et b
    paramètre:
        a : (int) entier relatif
        b : (int) entier relatif
    retour:
        un entier relatif
    """
    if b == 0:
        return a
    elif b > 0:
        return somme_rec(a, b-1) + 1
    else:
        return somme_rec(a, b+1) - 1
    
somme_rec(8, -5)
Out[20]:
3

Exercice 5

Comparaison de deux chaines de caractères
Ecrire de façon itérative, une fonction compare(chaine1,chaine2) qui renvoie le nombre de fois où chaine1 et chaine2 ont le même caractère au même emplacement.
A titre d'exemples :

  • compare("recursif","iteratif") renvoie 2,
  • compare("Python","Javascript") renvoie 0.
In [17]:
def compare(chaine1, chaine2):
    compteur = 0
    long = min(len(chaine1), len(chaine2))
    for i in range(long):
        if chaine1[i] == chaine2[i]:
            compteur += 1
    return compteur
In [18]:
compare("recursif","iteratif")
Out[18]:
2
In [19]:
compare("Python","Javascript")
Out[19]:
0
  1. Écrire cette même fonction de façon récursive.
In [21]:
def compare_rec(chaine1, chaine2):
    long = min(len(chaine1), len(chaine2))
    if long == 0:
        return 0
    else:
        if chaine1[0] == chaine2[0]:
            return 1 + compare_rec(chaine1[1:], chaine2[1:])
        return compare_rec(chaine1[1:], chaine2[1:])
In [22]:
compare_rec("recursif","iteratif")
Out[22]:
2
In [26]:
compare_rec("Python","Javascript")
Out[26]:
0

Exercice 6

Comprendre la récursivité

  1. Voici une fonction codée en Python :
In [29]:
def f(n):
    if n==0:
        print("Partez !")
    else:
        print(n)
        f(n-1)
f(5)

5
4
3
2
1
Partez !

a. Qu'affiche la commande f(5) ?

La commande affiche un compte à rebours de 5 à "Partez !"

b. Pourquoi dit-on de cette fonction qu'elle est récursive ?

La fonction est récursive car elle se rapelle elle même. De plus, on a : - on a une condition d'arrêt, - l'appel se rapproche de la condition d'arrêt.
  1. a. Recopier le code suivant en complétant la ligne 4
In [30]:
def ajouter(s,liste):
    res =  []
    for m in liste:
        res = res + [s + m]
    return res
In [31]:
ajouter("b",["a","b","c"])
Out[31]:
['ba', 'bb', 'bc']
In [32]:
ajouter("a",[""])
Out[32]:
['a']
  1. On s'intéresse ici à la fonction suivante écrite en Python où s est une chaîne de caractères et n un entier naturel.
In [35]:
def produit(s, n):
    if n == 0:
        return [""]
    else:
        res = []
        for i in range(len(s)):
            res = res + ajouter(s[i], produit(s, n-1))
    return res
In [36]:
produit("ab",0)
Out[36]:
['']
In [37]:
produit("ab",1)
Out[37]:
['a', 'b']
In [38]:
produit("ab",2)
Out[38]:
['aa', 'ab', 'ba', 'bb']
In [39]:
produit("ab",3)
Out[39]:
['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb']

Exercice 7

Mélange d'une liste

In [52]:
def echange(lst, i1, i2):
        c = lst[i2]
        lst[i2] = lst[i1]
        lst[i1] = c
In [57]:
l = [2,3,4,5]
In [54]:
echange(l,1,2)  
l
Out[54]:
[2, 4, 3, 5]
In [56]:
def echange2(lst, i1, i2):
    lst[i1],lst[i2] = lst[i2],lst[i1]
In [59]:
echange2(l,0,3)  
l
Out[59]:
[5, 4, 3, 2]

Exercice 8

Recherche dichotomique dans un tableau trié

  1. De façon itérative
In [1]:
def recherche_dichotomie(x, tableau):
    gauche = 0
    droite = len(tableau) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if tableau[milieu] == x:
            return True
        elif tableau[milieu] > x:
            droite = milieu - 1
        else:
            gauche = milieu + 1
    return False
In [2]:
T = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45]
recherche_dichotomie(9, T)
Out[2]:
False
In [3]:
T = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45]
recherche_dichotomie(14, T)
Out[3]:
True
  1. De façon recursive
In [4]:
def recherche_dichotomie_rec(x, tableau, gauche, droite):
    if gauche > droite:
        return False
    milieu = (gauche + droite) // 2
    if tableau[milieu] > x:
        return recherche_dichotomie_rec(x, tableau, gauche, milieu - 1)
    elif tableau[milieu] < x:
        return recherche_dichotomie_rec(x, tableau, milieu + 1, droite)
    else:
        return True
In [5]:
T = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45]
recherche_dichotomie_rec(40, T, 1, len(T))
Out[5]:
True
In [6]:
T = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45]
recherche_dichotomie_rec(-1, T, 1, len(T))
Out[6]:
False

Recherche la valeur et affiche l'indice ou -1 si la valeur n'est pas dans la liste

In [7]:
def indice_recursive(x, tableau, gauche, droite):
    if gauche > droite:
        return -1
    milieu = (gauche + droite) // 2
    if tableau[milieu] > x:
        return indice_recursive(x, tableau, gauche, milieu - 1)
    elif tableau[milieu] < x:
        return indice_recursive(x, tableau, milieu + 1, droite)
    else:
        return milieu
In [8]:
nombres = [2, 3, 5, 7, 11, 13, 17]
indice_recursive(13, nombres, 0, len(nombres)-1)
Out[8]:
5
In [9]:
T = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45]
indice_recursive(14,T , 0 , len(T)-1)
Out[9]:
3
In [10]:
indice_recursive(70,T , 0 , len(T)-1)
Out[10]:
-1

Exercices Complémentaires

  1. Calcul de pgcd de deux entiers positifs
In [11]:
def pgcd(a, b):
    """
    Calcule la pgcd de a et b
    paramètre:
        a : (int) entier >= 0
        b : (int) entier >= 0
    retour:
        un entier positif
    """
    if b == 0:
        return a
    else:
        r = a % b
        return pgcd(b, r)
In [12]:
pgcd(220, 12)
Out[12]:
4
In [18]:
# Version simplifiée

def pgcd_simp(a, b):
    """
    Calcule la pgcd de a et b
    paramètre:
        a : (int) entier >= 0
        b : (int) entier >= 0
    retour:
        un entier positif
    """
    if b == 0:
        return a
    else:
        return pgcd(b, a % b)
In [20]:
pgcd_simp(220, 12)
Out[20]:
4
In [16]:
# Autre version

def pgcd_bis(a, b):
    """
    Calcule la pgcd de a et b
    paramètre:
        a : (int) entier >= 0
        b : (int) entier >= 0
    retour:
        un entier positif
    """
    if a % b == 0:
        return b
    else:
        return pgcd(b, a % b)
In [17]:
pgcd_bis(220, 12)
Out[17]:
4
  1. Suite de Fibonacci
In [21]:
def fibo(n):
    """
    Calcule la valeur de la suite de Fibonacci pour n
    paramètre:
        n : (int) entier >= 0
    retour:
        un entier positif
    """
    if n == 0 or n == 1:
        return 1
    else:
        return fibo(n - 1) + fibo(n - 2)

for i in range(21):
    print(f"F({i}) = {fibo(i)}")
    #print("F(",i,") = ",fibo(i))

F(0) = 1
F(1) = 1
F(2) = 2
F(3) = 3
F(4) = 5
F(5) = 8
F(6) = 13
F(7) = 21
F(8) = 34
F(9) = 55
F(10) = 89
F(11) = 144
F(12) = 233
F(13) = 377
F(14) = 610
F(15) = 987
F(16) = 1597
F(17) = 2584
F(18) = 4181
F(19) = 6765
F(20) = 10946