Au programme :

Récursivité

• Ecrire un programme récursif
• Analyser le fonctionnement d’un programme récursif

Des exemples relevant de domaines variés sont à privilégier.

Exemple : somme des n premiers entiers

Classique

On peut écrire la somme des n premiers entiers de la forme :

$$\sum_{i=0}^{i=n}i = 0+1+2+...+n$$

Comment créer une fonction somme(n) qui implémente cette formule ? Il faut programmer la répétition (les $+ ... +$)

Boucle for

On peut utiliser une boucle for pour parcourir tous les entiers i entre 0 et n. Il faut donc aussi une variable intermédiaire t pour accumuler la somme des entiers, et retourner la valeur de cette variable à la fin.

def somme(n: int) -> int:
    assert n >= 0, "n doit être positif"
    t = 0
    for i in range(0,n+1):
        t += i
    return t

Difficulté

La formulation mathématique n’indique pas qu’il faut créer une variable t intermédiaire.

• c’est la difficulté de la programmation
• on peut donner une autre définition mathématique plus “simple”

Autre formulation

Définition d’une fonction mathématique somme(n) qui, pour tout $n\in\mathds{N}$ renvoie la somme des $n$ premiers entiers :

$$somme(n) = \begin{cases} 0 & \text{si } n=0\\ n+somme(n-1) & \text{si } n > 0\end{cases}$$

Exemple :

$$\begin{align*} somme(0) & = 0 & & & \\ somme(1) & = 1 + somme(1-1) & = 1 + somme(0) & = 1 + 0 &= 1 \\ somme(2) & = 2 + somme(2-1) & = 1 + somme(1) & = 2 + 1 &= 3 \\ somme(3) & = 3 + somme(3-1) & = 3 + somme(2) & = 3 + 3 &= 6 \end{align*}$$

Cette définition est récursive : c’est une définition de fonction qui fait appel à elle-même.

Avantages

Un des avantages est que l’implémentation en python est très proche de la définition de la fonction :

def somme(n: int) -> int:
    assert n >= 0, "n doit être positif"
    if n == 0:
        return 0
    return n + somme(n-1)

Analyse

Exécution du programme pas à pas pour somme(3)

• à la main
• en utilisant pythontutor

Arbre d’appel

Pour calculer somme(3), il faut avoir le résultat de somme(2), qui a besoin du résultat de somme(1), qui a besoin du résultat de somme(0). Le calcul est fait en quelque sorte “à l’envers” : l’arbre d’appel est le suivant :

somme(3) =
    return 3 + somme(2)
                 |
              return 2 + somme(1)
                           |
                        return 1 + somme(0)
                                     |
                                  return 0

Formulations récursives

Définition

Une formulation récursive d’une fonction est toujours constituée de plisieurs cas :

• les cas de base : ils permettent d’obtenir un résultat sans utiliser la fonction en cours de définition (souvent des valeurs particulières pour lesquelles il est facile de déterminer le résultat)
• les cas récursifs : ils font appel à la fonction en cours de définition

Exercice : puissance

Donner une définition récursive de $x^n$ et son implémentation.

Cas de base multiples

Plusieurs cas de base peuvent être donnés :

$$somme(n) = \begin{cases} 0 & \text{si } n=0\\ 1 & \text{si } n=1\\n+somme(n-1) & \text{si } n > 1\end{cases}$$

Cela peut être nécessaire, ou inutile (comme pour l’exemple ci-dessus)

Cas récursifs multiples

Plusieurs cas récursifs peuvent être donnés. Exemple, pour la suite appelée suite de Syracuse : https://fr.wikipedia.org/wiki/Conjecture_de_Syracuse

$$sy(n, k) = \begin{cases} k > 1 & \text{si } n=0\\ sy(n-1, k)/2 & \text{si } n>=1 \text{ et } sy(n-1, k) \text{ pair}\\ 3\times sy(n-1, k)+1 & \text{si } n>=1 \text{ et } sy(n-1, k) \text{ impair} \end{cases}$$

Exercice (maison) : implémenter def sy(n,k) et vérifier la conjecture de Syracuse pour tous les $k<100$.

Double (ou plus) récursion

Les expressions peuvent dépendre de plusieurs appels à la fonction en cours de définition. Exemple, la suite de Fibonnacci : https://fr.wikipedia.org/wiki/Suite_de_Fibonacci

$$fib(n) = \begin{cases} 0 & \text{si } n=0 \\ 1 & \text{si } n=1 \\ fib(n-2) + fib(n-1) & \ \text{ si} n > 1 \end{cases}$$

Exercice : écrire l’arbre d’appel de $fib(5)$; que peut-on dire du nombre d’opérations nécessaires pour calculer fib(n) ?

Récursion imbriquée

Les appels à la fonction en cours de définition peuvent parfois être imbriqués. Exemple : une fonction complètement tordue : la fonction $f_{91}$

$$f91(n) =\begin{cases} n-10 & \text{si } n > 100,\\ f91(f91(n+11)) & \text{si }n \leq 100. \end{cases}$$

Exercice : évaluer $f_{91}(99)$

Récursion mutuelle

Définition en même temps de deux fonctions récursives s’appelant l’une l’autre.

Définitions récursives bien formées

Règles à respecter

Les règles suivantes doivent être respectées pour qu’une fonction récursive soit bien écrite :

• s’assurer que la récursion va bien se terminer (qu’on retombe sur un des case de base)
• s’assurer que les arguments de la fonction sont toujours dans le domaine de la fonction
• s’assurer qu’il y a bien une définition pour toutes les valeurs du domaine.

Exemples - cas de base non atteint

$$f(n) =\begin{cases} 1 & \text{si } n = 0,\\ n+f(n+1) & \text{si }n \geq 0. \end{cases}$$

Le cas de base n’est jamais atteint

Exemples - domaine non respecté

$$g(n) = \begin{cases} 1 & \text{si } n=0, \\ n+g(n-2) & \text{si } n> 0. \end{cases}$$

$g(1)$ pose un petit problème…

Exemple - définitions manquantes

$$h(n) = \begin{cases} 1 & \text{si } n=0,\\ n+h(n-1) & \text{si } n>1. \end{cases}$$

Il manque un truc…

Exercices

Exo 1

Donner une définition récursive qui correspond au calcul de la fonction factorielle $n!$ définie par $n! = 1\times 2\times ···\times n$ si $n > 0$ et $0! = 1$, puis le code d’une fonction fact(n) qui implémente cette définition.

Exo 2

Écrire une fonction récursive $nombre\_de\_chiffres(n)$ qui prend un entier positif ou nul $n$ en argument et renvoie son nombre de chiffres. Par exemple, $nombre\_de\_chiffres(43321)$ doit renvoyer 5.

Indice : penser à la division par 10…