TP 5 : Récursivité

Principe général¶

On dit qu'une fonction est recursive lorsqu'elle s'appelle elle-même. Voici un exemple de fonction récursive :

In [21]:

def f(n):  # exemple de fonction récursive
    if n == 0:  # cas de base
        return
    print(n)
    f(n-1)
def f(n):  # exemple de fonction récursive
    if n == 0:  # cas de base
        return
    print(n)
    f(n-1)

Si n est différent de $0$, f(n) appelle f(n - 1). À ce moment, l'appel de f(n) se met en pause et f(n - 1) est exécuté. Lorsque l'appel à f(n - 1) est terminé, l'exécution de f(n) reprend là où elle s'était arrêté.

In [6]:

f(5)  # test
f(5)  # test

Lorsque on appelle f(5), print(5) est exécuté (d'où le 5 affiché) puis f(n - 1), qui affiche 4... jusqu'à l'appel de f(0) qui s'arrête sans faire d'affichage.
L'exécution de f(1) reprend alors, qui s'arrête, qui permet à f(2) de reprendre son calcul... jusqu'à f(5) qui s'arrête.
Ci-dessous, vous pouvez tester cet exécution étape par étape avec Python tutor :

Exercice

Qu'affiche le code suivant ? Le deviner puis vérifier.

def f(n):  # exemple de fonction récursive
    if n == 0:
        return
    f(n-1)
    print(n)

Une fonction récursive possède toujours :

Un (ou plusieurs) cas de base où la fonction renvoie directement une valeur, sans faire d'appel récursif. Sans cas de base, une fonction récursive ne s'arrête jamais (de la même façon qu'unwhile peut faire boucle infinie).
Un cas général où la fonction s'appelle récursivement sur un problème plus petit (par exemple pour $n- 1$) pour résoudre le problème (pour $n$).
L'écriture d'une fonction récursive ressemble donc beaucoup à une démonstration par récurrence : il faut ramener le problème à un sous-problème que l'on peut résoudre récursivement, et identifier un cas de base.

Exercice

Écrire une fonction récursive dessin tel que dessin(n) affiche le dessin ci-dessous, avec n lignes.

*****
****
***
**
*

On pourra utiliser print("*", end="") qui permet d'afficher * sans sauter de ligne (et print() pour sauter une ligne, quand nécessaire).

Solution

In [13]:

def dessin(n):
    if n == 0:
        return
    for i in range(n):
        print("*", end="")
    print()
    dessin(n-1)
dessin(5)
def dessin(n):
    if n == 0:
        return
    for i in range(n):
        print("*", end="")
    print()
    dessin(n-1)
dessin(5)

*****
****
***
**
*

Exercice

(plus difficile) : En utilisant une fonction récursive et avec une méthode similaire, dessiner une figure du genre suivant :

*
**
***
****
****
***
**
*

Solution

In [19]:

def dessin(k, n):
    if n == k:
        return
    for i in range(k):
        print("*", end="")
    print()

    dessin(k+1, n)
    for i in range(k):
        print("*", end="")
    print()

dessin(1, 5)
def dessin(k, n):
    if n == k:
        return
    for i in range(k):
        print("*", end="")
    print()

    dessin(k+1, n)
    for i in range(k):
        print("*", end="")
    print()

dessin(1, 5)

*
**
***
****
****
***
**
*

Applications simples¶

Exercice

En utilisant une boucle, écrire une fonction somme telle que somme(n) renvoie la somme des carrés des entiers de 1 à $n$ (c'est-à-dire $1^2 + 2^2 + 3^2 + ... + n^2$).

Solution

In [1]:

def somme(n):
    s = 0
    for i in range(n+1):
        s += i**2
    return s
def somme(n):
    s = 0
    for i in range(n+1):
        s += i**2
    return s

On peut aussi résoudre l'exercice précédent en remarquant que, en posant $S(n) = \displaystyle\sum_{k = 1}^n k^2$, on a l'équation de récurrence : $$S(n) = S(n - 1) + n^2$$ $$S(0) = 0$$ On peut donc en déduire une fonction récursive :

In [8]:

def somme(n):
    if n == 0:  # cas de base
        return 0
    else:  # cas général, où on utilise l'équation de récurrence
        return somme(n - 1) + n**2

somme(5)  # test
def somme(n):
    if n == 0:  # cas de base
        return 0
    else:  # cas général, où on utilise l'équation de récurrence
        return somme(n - 1) + n**2

somme(5)  # test

Out[8]:

Encore une fois, il peut être utile de visualiser l'exécution avec Python tutor :

Exercice

On souhaite calculer $n!$ ($= n\times (n - 1)\times ... \times 2\times 1$). Exprimer $n!$ en fonction de $(n - 1)!$.
En déduire une fonction récursive fact telle que fact(n) renvoie $n!$.

Solution

In [2]:

# 1.
# n! = n*(n - 1)!

# 2.
def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)
# 1.
# n! = n*(n - 1)!

# 2.
def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)

Dichotomie en récursif¶

On rappelle l'algorithme par dichotomie permettant de savoir si un élément e appartient à une liste L triée (revoir si besoin le TP précédent pour plus de détails) :

In [20]:

def dichotomie(e, L):
    i, j = 0, len(L) - 1  # i et j sont les indices de L entre lesquels on cherche e
    while i <= j: # tant qu'il reste au moins 1 élément entre les indices i et j
        m = (i + j)//2 # milieu de i et j
        if e < L[m]:
            j = m - 1 # regarder dans la partie gauche
        elif e > L[m]:
            i = m + 1 # regarder dans la partie droite
        else:
            return True # on a trouvé e
    return False # e n'a pas été trouvé
def dichotomie(e, L):
    i, j = 0, len(L) - 1  # i et j sont les indices de L entre lesquels on cherche e
    while i <= j: # tant qu'il reste au moins 1 élément entre les indices i et j
        m = (i + j)//2 # milieu de i et j
        if e < L[m]:
            j = m - 1 # regarder dans la partie gauche
        elif e > L[m]:
            i = m + 1 # regarder dans la partie droite
        else:
            return True # on a trouvé e
    return False # e n'a pas été trouvé

Exercice

Réécrire dichotomie sous forme de fonction récursive, en mettanti et j en arguments. Tester sur des exemples.

Solution

In [5]:

def dichotomie(e, L, i, j):
    if i > j:
        return False
    m = (i + j)//2
    if e < L[m]:
        return dichotomie(e, L, i, m - 1)
    elif e > L[m]:
        return dichotomie(e, L, m + 1, j)
    else:
        return True

L = [1, 4, 7, 11, 64]
assert dichotomie(1, L, 0, len(L) - 1) and not dichotomie(65, L, 0, len(L) - 1)
def dichotomie(e, L, i, j):
    if i > j:
        return False
    m = (i + j)//2
    if e < L[m]:
        return dichotomie(e, L, i, m - 1)
    elif e > L[m]:
        return dichotomie(e, L, m + 1, j)
    else:
        return True

L = [1, 4, 7, 11, 64]
assert dichotomie(1, L, 0, len(L) - 1) and not dichotomie(65, L, 0, len(L) - 1)