Récursivité - Correction exercices FICHE 2

    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 [4]:
def somme(n):
    assert n >= 0, "entrer un entier naturel"
    if n == 0:
        return 0
    else:
        return n + somme(n - 1)
In [5]:
somme(5)
Out[5]:
15
In [6]:
somme(-1)

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

<ipython-input-4-b514195a3042> in somme(n)
      1 def somme(n):
----> 2     assert n >= 0, "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 [7]:
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 [8]:
def somme(n):
    assert n >= 0, "entrer un entier naturel"
    return somme_bis(n)
In [9]:
somme(5)
Out[9]:
15
In [10]:
somme(-1)

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

<ipython-input-8-4a3635feae60> in somme(n)
      1 def somme(n):
----> 2     assert n >= 0, "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**. (Voir les ***exercices 8 et 9*** sur les puissances)

    Fiche 2

    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
    """
    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
    """
    produit = 1
    while n > 1:
        produit = produit * n
        n = n - 1
    return produit
In [14]:
fact_while(3)
Out[14]:
6

2) Fonction récursive

In [15]:
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 [16]:
fact_rec(5)
Out[16]:
120

Exercice 2

Calcul de pgcd de deux nombres entiers

In [17]:
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 [18]:
pgcd(220, 12)
Out[18]:
4

Exercice 3

Nombres d'adhérents
1)

In [19]:
def nombre(n):
    """
    Calcule le nombre théorique d'adhérents
    paramètre:
        n : (int) entier >= 1
    retour:
        un flotant positif
    """
    if n == 0:
        return 2000
    else:
        return nombre(n-1) * 0.95 + 200
In [20]:
nombre(10)
Out[20]:
2802.5261215232413

2) Nombres d'adhérents au cours des 20 prochaines années

In [21]:
for i in range(1, 21):
    print(nombre(i))

2100.0
2195.0
2285.25
2370.9874999999997
2452.4381249999997
2529.8162187499997
2603.3254078124996
2673.1591374218747
2739.5011805507806
2802.5261215232413
2862.399815447079
2919.279824674725
2973.3158334409886
3024.650041768939
3073.4175396804917
3119.746662696467
3163.7593295616434
3205.571363083561
3245.292794929383
3283.028155182914

Exercice 4

Suite de Fibonacci

In [22]:
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(fibo(i))

1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946

Exercice 5

In [23]:
# Version récursive normale
def somme_rec(a, b):
    """
    Calcule la somme 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 somme_rec(a, b-1) + 1

# Version récursive terminale
def somme_rec_term(a, b):
    """
    Calcule la somme 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 somme_rec_term(a+1, b-1)
In [24]:
somme_rec(3, 5)
Out[24]:
8
In [25]:
somme_rec_term(3, 5)
Out[25]:
8

Exercice 6

1) Version itérative

In [26]:
def somme(a, b):
    """
    Calcule la somme de a et b
    paramètre:
        a : (int) entier >= 0
        b : (int) entier >= 0
    retour:
        un entier positif
    """

    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[26]:
2

2) Version récursive normale

In [27]:
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(-3, 5)
Out[27]:
2

3) Version récursive terminale

In [28]:
def somme_rec_term(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_term(-3, 5)
Out[28]:
2

Exercice 7

Fonction paire

In [29]:
def pair(n):
    """
    Détermine si un nombre entier positif est pair
    paramètre:
        n : (int) entier >= 0
    retour:
        un booléen
    """
    if n > 0:
        return pair(n - 2)
    else:
        return n == 0
    
pair(8)
Out[29]:
True

Exercice 8

Fonction puissance
1) Version récursive normale

In [30]:
def puissance(x, n):
    """
    Calcule la puissance de x à l'exposant n
    paramètre:
        x : (flottant) 
        n : (int) entier relatif
    retour:
        un flottant
    """
    if n == 0:
        return 1
    else:
        return x * puissance(x, n-1)

puissance(7, 28)
Out[30]:
459986536544739960976801

2) Version récursive terminale - On utilise un accumulateur

In [31]:
def puissance(x, n, acc):
    """
    Calcule la puissance de x à l'exposant n
    paramètre:
        x : (float) 
        n : (int) entier relatif
        acc: (int) accumulateur
    retour:
        un flottant
    """
    if n == 0:
        return acc
    else:
        return puissance(x, n-1, x*acc)

puissance(7, 28, 1)
Out[31]:
459986536544739960976801

Exercice 9

Fonction puissance deuxième version

On peut cependant utiliser une autre définition de la fonction mathématique puissance(x, n) qui réduit drastiquement le nombre d’appels récursifs emboîtés.

D'après l'énoncé, on peut décomposer la fonction puissance en utilisant la fonction carre. On peut le faire avec deux cas récursifs qui distinguent la parité de n et deux cas de base (n = 0 et n = 1), comme ci-dessous :

puissance(x, n) =

1                   si n = 0,
x                   si n = 1,
carre(puissance(x, n//2))       si n > 1 et n est pair,
x * carre(puissance(x, (n - 1)//2))   si n > 1 et n est impair.


Pour le codage en Python

    L’appel à la fonction carre(x) est simplement remplacé par la multiplication r * r. Le test de parité est réalisé par un **test à zéro du reste de la division entière par 2** (soit r % 2 == 0).
In [32]:
def puissance(x,n):
    """
    Calcule la puissance de x à l'exposant n
    paramètre:
        x : (flottant) 
        n : (int) entier relatif
    retour:
        un flottant
    """
    if n == 0:
        return 1
    elif n == 1:
        return x
    else:
        r = puissance(x, n // 2)
        if n % 2 == 0:
            return r * r
        else:
            return x * r * r
In [33]:
puissance(7, 28)
Out[33]:
459986536544739960976801

Exercice 10

Fonction somme sur les élément d'une liste

1) On donne ici trois solutions possibles

In [40]:
def somme1(liste):
    """
   Calcule la somme des éléments d'une liste
    paramètre:
        liste : (list) une liste de nombres
    retour:
        un flottant
    """
    if liste == []:
        return 0
    else:
        return liste[0] + somme1(liste[1:])

def somme2(liste):
    """
    Calcule la somme des éléments d'une liste
    paramètre:
        liste : (list) une liste de nombres
    retour:
        un flottant
    """
    if liste == []:
        return 0
    else:
        return somme2(liste[:-1]) + liste[-1]
    

def somme3(liste):
    """
   Calcule la somme des éléments d'une liste
    paramètre:
        liste : (list) une liste de nombres
    retour:
        un flottant
    """
    if liste == []:
        return 0
    else:
        x = liste.pop() # Enlève et reourne la dernière valeur de la liste. la liste est modifiée etvide à la fin !
        return somme3(liste) + x
In [41]:
ex_liste = [4, 7, 2]
In [42]:
somme1(ex_liste)
Out[42]:
13
In [43]:
somme2(ex_liste)
Out[43]:
13
In [44]:
somme3(ex_liste)
Out[44]:
13

2) Explication du déroulement

On utilise la fonction somme1(list) et la liste ex_liste = [4, 7, 2] en paramètre.

- > en attente, doit renvoyer : 4 + somme1([7, 2])
--- > en attente, doit renvoyer : 4 + (7 + somme1([2]))
----- > en attente, doit renvoyer : 4 + (7 + (2 + somme1([])))
------- > arrêt des appels récursifs
------- > renvoi de somme1([]) : 4 + (7 + (2 + 0))
----- > renvoi de (2 + 0) : 4 + (7 + 2)
--- > renvoi de (7 + 2) : 4 + 9
--- > renvoi de 13

Exercice 11

Fonction mystere

1) On reconnait les divisions euclidiennes successives par 2.
A chaque étape, on garde le reste et on recommence avec le quotient.

Cette fonction renvoie donc l'écriture binaire de l'entier naturel n, sous la forme d'une chaîne de caractères.

2) On va utiliser une fonction à deux paramètres. D'après le cours de première, il suffit d'ajouter 2^n si r est négatif.
En utilisant la fonction mystere(n) de l'énoncé, on obtient :

In [45]:
def mystere(n):
    """
    Détermine l'écriture binaire d'un nombre entier naturel
    paramètre:
        n : (int) un entier naturel
    retour:
        chaîne de caractères
    """ 
    if n < 2:
        return str(n)
    else:
        return mystere(n//2) + str(n % 2)
In [46]:
mystere(18)
Out[46]:
'10010'

2) On va utiliser une fonction à deux paramètres. D'après le cours de première, il suffit d'ajouter 2^n si r est négatif.
En utilisant la fonction mystere(n) de l'énoncé, on obtient :

In [47]:
def binaire(r, n):  # on suppose -2**(n-1) <= n < 2**(n-1)
    """
    Détermine l'écriture binaire d'un nombre entier relatif
    paramètre:
        r : (int) entier relatif
        n : (int) un entier naturel stritement positif
    retour:
        chaîne de caractères
    """
    if r < 0:
        r = r + 2**n
    if r < 2:
        return str(r)
    else:
        return binaire(r//2, n) + str(r % 2)
In [48]:
binaire(18, 8)
Out[48]:
'10010'
In [49]:
binaire(-18, 8)
Out[49]:
'11101110'

3) Résultat codé avec n caractères. On peut avoir eventuellement des 0 au début.

In [50]:
def binaire(r, n, cpt = 0):  # on suppose -2**(n-1) <= n < 2**(n-1)
    """
    Détermine l'écriture binaire d'un nombre entier relatif
    paramètre:
        r : (int) entier relatif
        n : (int) un entier naturel stritement positif
        cpt: (int) compteur
    retour:
        chaîne de caractères
    """
    if r < 0:
        r = r + 2**n
    if r < 2:
        return (n -cpt - 1) * '0' + str(r)
    else:
        return binaire(r//2, n, cpt+1) + str(r % 2)
In [51]:
binaire(-18, 8)
Out[51]:
'11101110'

Exercice 12

Fonction inverse.
Cette fonction inverse une chaîne de caractères.

In [52]:
def inverse(ch):
    """
    Inverse l'ordre d'une chaîne de caractères
    paramètre:
        ch : (str) chaîne de caractères
    retour:
        chaîne de caractères
    """
    if ch == "":
        return ch
    else:
        return inverse(ch[1:]) + ch[0]
In [53]:
inverse("azerty")
Out[53]:
'ytreza'

Exercice 13

Fonction nettoie.
Cette fonction elimine les doublons dans une liste.

Version itérative de l'énoncé :

In [54]:
def nettoie(liste):
    """
    Elimine les doublons d'une liste
    paramètre:
        liste : (list) une liste de nombres
    retour:
        une liste
    """
    n = len(liste)
    k = 0
    while k < n - 1:
        if liste[k] != liste[k+1]:
            k = k + 1
        else:
            del liste[k]
            n = len(liste)

Version récursive :

In [55]:
def nettoie_rec(liste, k = 0):
    """
    Elimine les doublons d'une liste
    paramètre:
        liste : (list) une liste de nombres
    retour:
        une liste
    """
    if k < len(liste) - 1:
        if liste[k] != liste[k+1]:
            nettoie_rec(liste, k+1)
        else:
            del liste[k]
            nettoie_rec(liste, k)
In [56]:
ex_liste = [1, 1, 2, 6, 6, 6, 8, 8, 9, 10]
nettoie(ex_liste)
ex_liste
Out[56]:
[1, 2, 6, 8, 9, 10]
In [57]:
ex_liste = [1, 1, 2, 6, 6, 6, 8, 8, 9, 10]
nettoie_rec(ex_liste)
ex_liste
Out[57]:
[1, 2, 6, 8, 9, 10]
In [ ]: