• 4 heures
  • Facile

Ce cours est visible gratuitement en ligne.

Ce cours est en vidéo.

Vous pouvez obtenir un certificat de réussite à l'issue de ce cours.

J'ai tout compris !

Mis à jour le 20/05/2019

Voyez le monde autrement avec la récursivité

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Dans ce chapitre, nous allons explorer un nouveau mode de calcul : la récursivité.

En programmation, nous avons vu que nous pouvions utiliser des boucles pour répéter une opération. Nous les appelons des boucles itératives. Laissez-moi vous présenter un nouveau concept : la récursivité.

Il s’agit d’un concept un peu spécial. Avez-vous déjà rêvé que vous rêviez ? Vous y êtes ! Nous allons parler de concepts qui s’appellent eux-mêmes. C’est parti !

Présentation

La récursivité est un concept qui fait référence à lui-même dans son fonctionnement. Cela se retrouve dans tous les champs artistiques : littérature (mise en abyme), peinture, photographie...

Jan Van Eyck, Les Epoux Arnolfini
Jan Van Eyck, Les Époux Arnolfini
Mirroirs
Miroirs

Nous utilisons d’ailleurs tous les jours la récursivité lorsque nous définissons des mots ! En effet, nous utilisons des mots pour en définir d’autres, eux-mêmes étant définis par d’autres mots !

Pour les fans de Wall-E, c’est également un procédé utilisé par le Capitaine de l’Axiom !

En programmation

En programmation, il s’agit d’une fonction qui fait référence à elle-même. Deux fonctions peuvent s’appeler l’une l’autre, on parle alors de récursivité croisée.

Une fois n’est pas coutume, utilisons un exemple du monde des mathématiques : les factorielles. Une factorielle d’un entier naturel n est le produit des nombres entiers strictement positifs inférieurs ou égaux à n.

Elle est notée n! et se calcule ainsi : n! = (n-1)! * n.

Exemple : la factorielle 10!

1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10 = 3 628 800

Comment la programmer ?

Réalisons un premier essai en Python :

def factorielle_recursive(n):
    return n*factorielle_recursive(n-1)

Déroulez cet algorithme dans votre tête : vous vous apercevrez qu’il ne s’arrête jamais et qu’il tourne à l’infini ! En effet, si on lance la fonction avec n=3factorielle_recursive(n) sera appelée avec n=3, puis n=2, puis n=1, puis n=0, puis n=-1, etc.

Un algorithme qui ne s’arrête jamais, c’est un problème, vous vous en doutez bien !

La solution est donc de spécifier une condition d’arrêt, qui dépendra toujours de notre problème. Dans notre cas, 3!= 3*2*1. Vous remarquez que les différents facteurs (3, 2 et 1) ne sont jamais négatifs ni même égaux à 0. C’est précisément cette condition qui nous servira de condition d’arrêt : "le facteur ne doit jamais être ni inférieur ni égal à 0".

Ainsi, nous ajoutons une instruction conditionnelle :

def factorielle_recursive(n):
    if n <= 1:
        return 1
    else:
        return n*factorielle_recursive(n-1)

Un appel récursif doit obligatoirement être dans une instruction conditionnelle.

Nous aurions également pu implémenter la fonction factorielle de manière itérative :

def factorielle_iterative(n):
    x = 1
    for i in range(2, n+1):
        x *= i
    return x

Suite de Fibonacci

Avez-vous déjà passé un entretien d’embauche technique pour travailler en tant que développeur·se, par exemple ? Si oui, la suite de Fibonacci vous parlera certainement ! Il s’agit d’un des problèmes les plus couramment posés en entretien.

La suite de Fibonacci est une liste de nombres entiers. Elle commence généralement par les nombres 0 et 1 (parfois 1 et 1). On appelle un nombre de cette liste un terme. Chaque terme est la somme des deux termes qui le précèdent.

Par exemple, si la suite de Fibonacci débute ainsi : 0, 1, 1, 2, 3, 5, 8, 13, 21, etc., vous voyez que 0 + 1 donne 1, que 1 + 2 donne 3, que 3 + 5 donne 8, et ainsi de suite.

Il existe plusieurs manières de résoudre le problème lié à la suite de Fibonacci. Prenez quelques minutes pour réfléchir aux différents algorithmes que vous pourriez inventer.

Dans ce chapitre, nous allons utiliser une méthode récursive et une méthode itérative afin que vous puissiez comparer les deux possibilités !

Algorithme récursif naïf

Un algorithme naïf désigne un algorithme "simple", très proche de notre pensée quotidienne. Concrètement, il s’agit de la première manière qui vous vient à l’esprit de résoudre un problème.

Dans notre cas, nous pouvons dire :

fonction fibonacci(n):
  si n <= 1
    renvoie 1
  sinon
    renvoie fibonacci(n-1) + fibonacci(n-2)

fibonacci(10)
# renverra 89

En Python :

def fibo(n):
    if n <= 1:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

Le problème dans ce cas est que nous consommons beaucoup de mémoire. En effet, le calcul est exponentiel : il demande deux calculs différents pour se calculer lui-même.

Quand nous calculons la valeur d’un nombre, nous réalisons les trois opérations suivantes :

  • calcule fibonacci(n-1) [qui lui-même va calculer fibonacci(n-1) et ainsi de suite jusqu’à arriver au chiffre 1] et garde la valeur en mémoire ;

  • calcule fibonacci(n-2) [fais-en de même à chaque fois jusqu’à arriver à 1] et garde la valeur en mémoire ;

  • enfin, ajoute les deux précédentes valeurs.

Nous voyons par conséquent que ce calcul est exponentiel : chaque nouveau nombre demande deux fois plus de mémoire que son précédent. Sa complexité est de O(2^n).

Peut-on trouver une manière moins consommatrice de le calculer ?

Algorithme linéaire

Et si vous calculiez deux valeurs consécutives à la suite ? Cela serait mieux, non ?

def fibo(n):
    a,b = 0,1
    for i in range(1, n+1):
        c = a + b
        print(b)
        a = b
        b = c

À présent, chaque nouveau nombre n’a plus besoin de deux niveaux d’opération pour le générer, mais d’un seul. Il est donc linéaire et sa complexité est de O(n).

Nous voyons ici que, dans bien des cas, nous préférerons la version itérative, car elle est moins consommatrice en mémoire.

Les piles d’appels

L’ordinateur doit retenir le résultat de tous les calculs récursifs avant de finir sa boucle. Il utilise alors ce que nous appelons une "pile d’appels" (en anglais, stack). Celle-ci est gérée automatiquement par le système.

Dans le cas d’un appel récursif, c’est exactement ce qui se passe ! Lorsque nous calculons une factorielle, nous devons exécuter n(-1)! puis n(-2)! puis n(-3)! jusqu’à arriver au nombre que nous souhaitons calculer. L’ordinateur va donc empiler les résultats de n(-1)!, puis de n(-2)!, de n(-3)! etc.

valeur de n

résultat dans la pile

n(-9)

1

n(-8)

2

n(-7)

3

n(-6)

4

n(-5)

5

n(-4)

6

n(-3)

7

n(-2)

8

n(-1)

9

n

10

Lorsque la dernière fonction récursive est appelée, l’ordinateur "dépile". Autrement dit, il va chercher dans la pile le dernier élément enregistré et ainsi de suite jusqu’à arriver en bas de la pile. Bien pratique !

En résumé : comment programmer une fonction récursive ?

1/ Décomposer le problème en un ou plusieurs sous-problèmes du même type. On résout les sous-problèmes par des appels récursifs.

2/ Les sous-problèmes doivent être de taille plus petite que le problème initial.

3/ Enfin, la décomposition doit en fin de compte conduire à un élémentaire qui, lui, n’est pas décomposé en sous-problèmes (c’est la condition d’arrêt).

Structure d’une fonction récursive :

mafonction(param1, param2):
    début
        si condition faire
            retourner calcul
        sinon faire
            mafonction(param1, param2)
            retourner quelque-chose
        fin condition faire
    fin
fin ma fonction
Exemple de certificat de réussite
Exemple de certificat de réussite