RÉCURSIVITÉ

1 - Exemples et contre-exemples

?

def Factorielle(x) :
    if x == 0 :
        return 1
    else :
        return x * Factorielle(x - 1)

?

def ?
?

def PGCD(x, y) :
    if y == 0 :
        return x
    else :
        return PGCD(y, x % y)

?

def PGCD(x, y) :
    def Aux(x_, y_) :
        if y_ == 0 :
            return x_
        else :
            return Aux(y_, x_ % y_)
    return Aux(abs(x), abs(y))

?


?

def Binomial(n, k) :
?

def Binomial(n, k) :
    def Aux(n_, k_) :
        if k_ == 0 :
            return 1
        else :
            return n_ * Aux(n_ - 1, k_ - 1) // k_
    if k < 0 or k > n :
        return 0
    else :
        return Aux(n, min(k, n - k))

?

def ?
?

def Dichotomie(f, a, b, ε) :
?

2 - Lien avec les suites récurrentes

a) Les cas simples : un seul appel récursif

?

def ?
?

def ?
?

def ?

b) Plusieurs appels récursifs

Considérons la suite logistique : elle utilise un paramètre \(\mu\) dans \(\left[0\,;\,4\right]\), son premier terme \(u_0\) est entre zéro et un, et elle satisfait la relation de récurrence \[ u_{n + 1} = \mu \times u_n \times (1 - u_n). \] Programmons cela naïvement.

def u(µ, n) :
    if n == 0 :
        return 0
    else :
        return µ * u(µ, n - 1) * (1 - u(µ, n - 1))

Rappelons le programme

from time import time as Maintenant
def Chronométrer(Programme, *Entrées) :
    début = Maintenant()
    Sortie = Programme(*Entrées)
    fin = Maintenant()
    return fin - début

et utilisons-le pour voir ce qui se passe. On choisit \(\mu = 2,\!5\) mais sa valeur n'a aucune incidence sur le temps d'exécution : seule la valeur de \(n\) joue.

>>> Chronométrer(u, 2.5, 20)
?
>>> Chronométrer(u, 2.5, 21)
?
>>> Chronométrer(u, 2.5, 22)
?

?

def u(µ, n) :
    if n == 0 :
        return 0
    else :
        préc = u(µ, n - 1)
        return µ * préc * (1 - préc)

def ?
La suite de Fibonacci.

def ?
Autres récurrences d'ordre deux.

def ?
Récurrences (pas forcément linéaires) d'ordre quelconque.

def ?
? ?


c) Les cas difficiles : appels récursifs pêle-mêle

?

def ?
?


3 - Exponentiation rapide

a) Ce que c'est, et sa version récursive

L'exponentiation, c'est le nom de l'opération effectuée pour calculer les puissances. Le calcul naïf de \(x^n\) se fait avec \(n - 1\) multiplications : \[ x^n = \underset{\text{$n$ fois le nombre $x$}}{\underbrace{x \times x \times x \times \dots \times x}}. \] On va voir qu'on peut faire beaucoup mieux. En effet, en notant \(y = x^{\left\lfloor n/2 \right\rfloor}\), on a \[ x^n = \left\{\begin{array}{cl} 1 & \text{si $n = 0$,} \\ y \times y & \text{si $n$ est pair,} \\ x \times y \times y & \text{si $n$ est impair.} \end{array}\right. \] Traduisons déjà ceci en Python.

def Puissance(x, n) :
    if n == 0 :
        return 1
    else :
        y = Puissance(x, n // 2)
        if n % 2 == 0 :
            return y * y
        else :
            return x * y * y

Généralisons cela à une opération quelconque.

def Puissance(x, n, op, e) :
    if n == 0 :
        return e
    else :
        y = Puissance(x, n // 2, op, e)
        if n % 2 == 0 :
            return op(y, y)
        else :
            return op(x, op(y, y))

?

def ExponentiationRapide(op, e) :
    def Puissance(x, n) :
        if n == 0 :
            return e
        else :
            y = Puissance(x, n // 2)
            if n % 2 == 0 :
                return op(y, y)
            else :
                return op(x, op(y, y))
    return Puissance

b) Version non récursive

Pour écrire la version non récursive, il faut réfléchir un peu plus. On utilise l'écriture binaire de l'exposant \(n = \overline{n_{r-1}n_{r-2}\dots{}n_1{}n_0}_{(2)}\) pour obtenir la formule \[ x^n = x^{\left(\displaystyle{\sum_{i = 0}^{r - 1}n_i 2^i}\right)} = \prod_{i = 0}^{r - 1} x^{n_i 2^i} = \prod_{i = 0}^{r - 1} \left(x^{2^i}\right)^{n_i}. \] Mais puisque les \(n_i\) valent zéro ou un, dans le dernier produit, ne restent que les facteurs pour lesquels \(n_i = 1\), et on obtient \[ x^n = \prod_{n_i = 1} x^{2^i}. \] Il reste, avant de traduire cela en Python, à remarquer que \(x^{2^{i + 1}} = (x^{2^i})^2\). Dans le programme ci-dessous, la variable y représente cette quantité ; elle sera donc élevée au carré à chaque itération.

def ExponentiationRapide(op, e) :
    def Puissance(x, n) :
        p = e ; y = x ; n_ = n
        while n_ > 0 :
            if n_ % 2 == 1 :
                p = op(p, y)
            y = op(y, y) ; n_ //= 2
        return p
    return Puissance

?

c) Récurrences linéaires d'ordre quelconque

?

def ?
?