Aller au contenu

N. Récursivité

Objectif

L'objectif de ce chapitre est de rencontrer et de se familiariser avec un principe de programmation classique : la récursivité.

I. Le concept

On a déjà vu le principe d'utilisation des fonctions qui se déroule en deux temps :

  • on commence par définir la fonction avec notamment le mot clé def
  • ensuite on l'appelle (avec son nom et les paramètres nécessaires) quand on en a besoin

Certains langages (la plupart d'ailleurs) permettent à une fonction de s'appeler elle-même, on parle alors de récursivité (comme en math avec les suites récurrentes par exemple). Voyons les possibilités offertes par ce concept...

1. Un exemple graphique pour comprendre

La fonction triangle ci-dessous permet comme son nom l'indique de dessiner un triangle rempli d'étoiles. Le principe repose sur le fait que pour dessiner un triangle avec \(n\) lignes, il suffit de savoir dessiner un triangle avec \(n-1\) lignes et d'en rajouter une:

def triangle1(n):
    if n==1 :
        print('*')
    else :
        print('*'*n) #affiche n caractères '*'
        triangle1(n-1)

triangle1(5)

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

Remarque importante :

Puisqu'une fonction récursive s'appelle elle-même, il est indispensable de prévoir une condition d'arrêt à la récursion (ici le if n==1), sinon le programme ne s'arrêtera jamais.

La fonction récursive teste (souvent en premier) la condition d'arrêt puis, si la condition n'est pas vérifiée, lance un appel récursif.

Visualisation des appels récursifs

Il est instructif de visualiser les étapes successives lors de l'exécution du code précédent. Pour cela il existe un site fort intéressant python tutor. Aller sur ce site et copier/coller votre code pour visualiser son exécution pas à pas. Remarquer l'empilement des appels à la fonction triangle1.

Pour voir si on a compris !

Dans la fonction triangle1 précédente, on fait dessiner avant de rappeler la fonction. Écrire une fonction triangle2 en inversant les lignes 5 et 6, essayer d'anticiper ce qui va être affiché, tester pour contrôler, puis visualiser l'exécution avec python tutor.

def triangle2(n):
    if n==1 :
        print('*')
    else :
        triangle2(n-1)  
        print('*'*n) #affiche n caractères '*'


triangle2(5)

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

2. Un exemple avec return

En pratique : dans l'exemple précédent, notre fonction (pour faire simple), se contentait de dessiner à l'écran, mais en principe, le rôle d'une fonction est de renvoyer quelque chose (mot clé return). Cela peut permettre de faire des calculs récursifs.

Calcul du n-ième nombre triangulaire

Par exemple voyons comment calculer le n-ième nombre triangulaire, c'est à dire le nombre d'étoiles dessinées dans le triangle à \(n\) lignes. Compléter le code suivant afin qu'il affiche le n-ième nombre triangulaire:

def triangle3(n):
    if n == 1 :
        return 1
    else :
        return triangle3(n-1)+n

N=5
print(f"T({N})={triangle3(N)}")

# Résultat :
T(5)=15

3. Une vidéo INRIA : "le crêpier psychorigide"

Pour illustrer ce nouveau concept de programmation (la récursivité), consulter la vidéo faite par l'INRIA, sur le crêpier psychorigide

Pour info, voici un code python traduisant la méthode du crêpier psychorigide :

""" Le crepier psycho-rigide 
Ici, les crepes sont représentées par des entiers. Le signe positif
détermine une crêpe à l'endroit, alors qu'un signe négatif est une crêpe
à l'envers. La valeur absolue donne la taille de la crêpe.
"""

def retourner(tas,pos):
    """ 
        renverse les éléments depuis la position pos
        jusqu'à la fin et renvoie le nouveau tas 
    """
    new_tas = tas[:pos]
    temp = [-i for i in reversed(tas[pos:])]
    new_tas.extend(temp)
    return new_tas

def trier(tas):
    tas_abs = [abs(i) for i in tas]
    i_max = tas_abs.index(max(tas_abs))
    tas = retourner(tas,i_max)
    if tas[-1] > 0 :
        tas = retourner(tas,-1)
    tas = retourner(tas,0)
    print(tas[0])
    tas = tas[1:]
    if len(tas)>1 :
        trier(tas)
    else : 
        print(abs(tas[0]))

a = [-3 , 2, -6 , 1]
print("liste des crepes au debut : ", a)

trier(a)

II. Complexité en espace

1. Un exemple : approximation du nombre d'or

Vous connaissez déjà probablement le nombre d'or que l'on note souvent \(\varphi\) et qui apparait dans de nombreux domaines liés à l'esthétisme (voir par exemple le nombre d'or sur Wikipedia). Parmi les curiosités, voici ci-dessous une manière originale d'approcher sa valeur:

\[\varphi = 1+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{1+\ldots}}}\]

Mathématiquement, l'objet précédent s'appelle une fraction continue. Pour la calculer, cela revient à déterminer la limite de la suite \((u_n)\) définie par récurrence:

\[\left\{ \begin{array}{l} u_1 = 1\\ u_{n+1} = 1 + \dfrac{1}{u_n} \end{array}\right.\]

Calcul de \(\varphi\) par une méthode itérative

Sans utiliser le concept de récursivité, écrire une fonction python u(n : int) -> float qui renvoie le n-ième terme de la suite \((u_n)\) et calculer \(u(5)\), \(u(10)\) et \(u(100)\) :

# Version itérative

def u(n : int) -> float :
    assert n >= 1
    u = 1
    for _ in range(2,n+1) :
        u = 1 + 1/u
    return u

for n in [1,2,5,10,100]:
    print(f"u({n})={u(n)}")

u(1)=1
u(2)=2.0
u(5)=1.6
u(10)=1.6181818181818182
u(100)=1.618033988749895

Calcul de \(\varphi\) par une méthode récursive

En utilisant le principe de récursivité, écrire un nouveau code (peut-être plus naturel ?) pour calculer les termes de la suite \((u_n)\).

def u_rec(n :int) -> float :
if n == 1 :
    return 1
else :
    return 1+1/u_rec(n-1)

for n in [1,2,5,10,100]:
    print(f"u({n})={u(n)}")

u(1)=1
u(2)=2.0
u(5)=1.6
u(10)=1.6181818181818182
u(100)=1.618033988749895

Remarque : Exécuter votre code avec u_rec(5) sur le site python tutor et constater que l'on empile 5 fois la fonction en mémoire...

2. Deuxième exemple : la suite de Fibonacci

Pour se rendre compte du problème, regardons de plus près le calcul des termes de la suite emblématique de Fibonacci:

\[ \left\{ \begin{array}{l} F_0=F_1=1\\ F_n = F_{n-1}+F_{n-2} \end{array} \right.\]

Une façon simple de programmer le calcul de cette suite est d'utiliser le principe de récursivité de la façon suivante :

def fibo1(n : int) -> int:
    """ calcule le n-ieme terme de la suite de Fibonacci"""
    if n==0 or n==1 : # test d'arrêt
        return 1
    else :
        return fibo1(n-1)+fibo1(n-2)

n=5
print(f"F({n})={fibo1(n)}")

# Résultat
F(5)=8

Pour évaluer le nombre d'appels faits on peut introduire (comme dans le TD sur la complexité) une variable globale de la façon suivante :

def fibo1(n : int) -> int:
    """ calcule le n-ieme terme de la suite de Fibonacci par une méthode récursive"""
    global c
    c += 1
    if n==0 or n==1 : # test d'arrêt
        return 1
    else :
        return fibo1(n-1)+fibo1(n-2)

for n in [2,3,4,5,10] :
    c = 0
    fibo1(n)
    print(f"Nombre d'appels récursifs pour calculer F({n}) : {c}")

Nombre d'appels récursifs pour calculer F(2) : 3
Nombre d'appels récursifs pour calculer F(3) : 5
Nombre d'appels récursifs pour calculer F(4) : 9
Nombre d'appels récursifs pour calculer F(5) : 15
Nombre d'appels récursifs pour calculer F(10) : 177

On constate que pour évaluer \(F_n(5)\) on fait 15 appels à la fonction. Tester la fonction fibo1 sur python tutor pour voir ce qu'il se passe.

Pour comprendre ce qu'il se passe on peut représenter ce que l'on appelle l'arbre des appels récursifs:

arbre_rec.png

Première conclusion

Cette façon de programmer est dans ce cas inefficace en nombres d'appels et en occupation mémoire (elle calcule plusieurs fois les même choses !)

Elle est de plus inutilisable si \(n\) est grand...

Remarque : pour obtenir un bien plus grande efficacité pour calculer les termes de la suite de Fibonacci, il sera préférable (au détriment de la simplicité d'écriture) de programmer une version itérative, par exemple comme cela :

def fibo2(n : int)-> int :
    """ calcule le n-ieme terme de la suite de Fibonacci par une méthode itérative"""
    if n==0 or n==1 :
        return 1
    uprec , ucour = 1 , 1
    for i in range(2,n+1):
        uprec , ucour = ucour , uprec+ucour
    return ucour

n=5
print(f"F({n})={fibo1(n)}")

Pour info : voici la question Q24 du sujet CCINP math 2024 :

CCINP_2024_Q24_python_fibonacci.png

Conclusion

Les algorithmes écrits sous forme récursive sont en principe élégants, simples à concevoir mais souvent d'une performance médiocre et peu adaptée pour un utilisation avec des données de grande taille. La complexité est souvent exponentielle (\(O(a^n)\)) ce qui empêche de travailler pour des valeurs de \(n\) au delà de 50...

III. Pour aller plus loin

On pourra se balader sur un site très complet et très visuel avec beaucoup d'exemples : site de Mickaël Péchaud

IV. Le TD

Pour se familiariser avec cette notion importante et pas toujours facile à maîtriser, on va rencontrer quelques exemples classiques en TD.

TD N1 version interactive capytale

Versions html : Énoncé et Correction (à venir)