Algorithmes récursifs

Frédéric Herbreteau, Bordeaux INP/LaBRI (frederic.herbreteau@bordeaux-inp.fr)

Calcul itératif de la factorielle

Définition: la factorielle de $n \in \mathbb{N}$ est définie par $n! = \left(\prod_{i=1}^n i\right) = 1 \times \ldots \times n$

def factorielle(n: int) -> int:
    assert n >= 0
    f = 1
    for i in range(1,n+1): # ou même range(2, n+1)
        f = f * i
    return f

terminaison: n itérations de la boucle for
correction: $f = (i-1)!$ est un invariant de la boucle for
complexité: $\Omicron(n)$ opérations arithmétiques, et espace $\Omicron(1)$

Calcul récursif de la factorielle

Définition alternative: la factorielle de $n \in \mathbb{N}$ est le terme de rang $n$ dans la suite: $u_0 = 1$ $u_n = u_{n-1} \times n$ pour $n \ge 1$

def factorielle(n: int) -> int:
    assert n >= 0
    if n == 0:
        return 1
    else:
        return factorielle(n-1) * n

illustrer le calcul pour $n=5$

Conception des algorithmes récursifs

Qu’est-ce qu’un algorithme récursif?

Définition: Un algorithme est récursif si pour résoudre un problème $P$ sur une certaine instance $a$, il s’appuie sur la résolution du même problème $P$ sur une autre instance $b$.

def factorielle(n: int) -> int:
    assert n >= 0
    if n == 0:
        return 1
    else:
        return factorielle(n-1) * n

Définition: un appel récursif est une étape où l’algorithme résout le même problème sur une autre instance

Conception des algorithmes recursifs

Un algorithme récursif comprend toujours:

un ou des appels récursifs du même algorithme sur des instances généralement plus petites
un ou des cas d’arrêt

def fact(n: int) -> int:
    return n * fact(n - 1)

def fact2(n: int) -> int:
    if n == 0:
        return 1
    else:
        return n * fact2(n + 1)

Exercice 1

La suite de Fibonacci est définie par: $F_0 = 0$ $F_1 = 1$ $F_n = F_{n-1} + F_{n-2}$ pour $n \ge 2$

Mettre en oeuvre un algorithme récursif qui calcule $F_n$:

def fibonacci(n: int) -> int:

illustrer le calcul pour $n=5$

Terminaison des algorithmes récursifs

Un algorithme récursif termine s’il existe une suite:

strictement décroissante pour chaque appel récursif

et à valeurs dans $\mathbb{N}$

def factorielle(n: int) -> int:
    assert n >= 0
    if n == 0:
        return 1
    else:
        return factorielle(n-1) * n

PRECOND: $n \in \mathbb{N}$

Correction des algorithmes récursifs

Prouver que la spécification est respectée, en supposant que les appels récursifs sont corrects (preuve par récurrence sur les appels récursifs)

def factorielle(n: int) -> int:
    assert n >= 0
    if n == 0:
        return 1
    else:
        return factorielle(n-1) * n

PRECOND: $n \in \mathbb{N}$
POSTCOND: factorielle(n) retourne $n!$

Complexité des algorithmes récursifs

La complexité en temps et en espace dépend du nombre d’apppels récursifs

def factorielle(n: int) -> int:
    assert n >= 0
    if n == 0:
        return 1
    else:
        return factorielle(n-1) * n

Calculer la complexité en temps et en espace de la fonction factorielle
Comparer à la complexité de l’algorithme itératif

Exercice 2

Prouver la terminaison et la correction de la fonction fibonacci
- PRECOND: $n \in \mathbb{N}$
- POSTCOND: fibonacci(n) retourne $F_n$
Calculer la complexité en temps et en espace de la fonction fibonacci

def fibonacci(n: int) -> int:
    assert n >= 0
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Types de récursivité

Récursivité terminale

Définition: un algorithme est récursif terminal s’il retourne directement les valeurs de ses appels récursifs, sans réaliser d’opérations sur celles-ci

l’algorithme factorial vu précédemment n’est pas récursif terminal

Version récursive terminale à appeller avc: x = factorielle_temrinale(n, 1):

def factorielle_terminale(n: int, f: int) -> int:
    assert m >= 0
    if n == 0:
        return f
    else:
        return factorielle_terminale(n - 1, f * n)

un algorithme récursif terminal se transforme facilement en algorithme itératif (certains compulateurs le font automatiquement)

Récursivité mutuelle

Définition: deux algorithmes (ou plus) sont mutuellement récursifs s’ils font appel les uns aux autres

def pair(n: int) -> bool:
    assert n >= 0
    if n == 0:
        return True
    else:
        return impair(n-1)

def impair(n: int) -> bool:
    assert n >= 0
    if n == 0:
        return False
    else:
        return pair(n-1)

Exercices supplémentaires

Exercice 3

Écrire une fonction récursive qui calcule le terme de rang n d’une suite arithmétique de raison r et de premier terme p

def arithmetique(n: int, r: int, p: int) -> int:

Écrire une fonction récursive qui calcule le terme de rang n d’une suite géométrique de raison r et de premier terme p

def geometrique(n: int, r: int, p: int) -> int:

Justifier la terminaison et la correction des deux fonctions. Évaluer leurs complexités en temps et en espace

Exercice 4

Écrire une fonction récursive qui calcule $x^n$ pour un nombre flottant x et un entier naturel n

def puissance(x: float, n: int) -> float:

Justifier la terminaison et la correction de la fonction. Évaluer sa complexité en temps et en espace
Proposer une fonction récursive de complexité $\Omicron(\log_2(n))$ en temps et en espace

def puissance_rapide(x: float, n: int) -> float:

Exercice 5

Écrire une fonction récursive qui calcule le nombre de chiffres d’un entier naturel n

def nb_chiffres(n: int) -> int:

Écrire une fonction récursive qui calcule la somme des chiffres d’un entier naturel n

def somme_chiffres(n: int) -> int:

Justifier la terminaison et la correction des deux fonctions. Évaluer leurs complexités en temps et en espace