La récursivité est très souvent oubliée lors de l'apprentissage d'un langage de programmation, non pas parce qu'elle est difficile à comprendre et à apprendre, mais parce qu'elle est peu connue. Pourtant, celle-ci peut se révéler d'une extrême importance. Le but de cet article est donc de vous faire part de cette fonctionnalité.

Qu'est-ce que la récursivité ?

Un algorithme est dit récursif si, à un moment, il s'appelle lui-même. Pour mieux comprendre, prenons le cas de la fonction récursive car c'est l'application de la récursivité la plus courante et que c'est celle que nous utiliserons par la suite. Par conséquent, une fonction récursive est une fonction qui s'auto-appelle. Voici un petit exemple :

def f(x):
    x = 2 * x
    f(x)
    return x

Nous voyons bien que la fonction f s'appelle elle même à la ligne 3. En réalité, voilà comment l'ordinateur agit :

def f(x):
    x = 2 * x
        x = 2 * x
            x = 2 * x
                x = 2 * x
                    x = 2 * x
                        ...
    return x

Avant de voir les différentes applications de la récursivité, notons que ce code n'a aucune utilité car il ne se finirait jamais, la fonction f étant indéfiniment appelée.

La récursite : incontournable dans certains cas

La récursivité peut posséder de nombreux avantages dans un algorithme. Premièrement, elle permet de résoudre des problèmes, d'habitude irrésolvables avec l'utilisation de simples boucles pour ou tant que. Elle peut aussi rendre un algorithme plus lisible et plus court, mais surtout, elle permet, dans certains cas, un gain colossal de temps comme c'est le cas dans les algorithmes de tri.

Pour mieux s'en rendre compte, nous allons aborder deux algorithmes de tri différents qui ont pour but, comme leur nom l'indique, de trier des données, ici, ce sera des chiffres. Et nous allons voir que, certes, nous obtiendrons, au final, la même liste de nombres triée, mais que, cependant, le temps d'obtention ne sera absolument pas le même. On prendra, comme valeurs de départ, une liste de nombres tirés au hasard, soit une liste non triée.

Le tri par sélection ou par minimums successifs

Le tri par sélection est vraisemblablement l'algorithme de tri le plus simple à comprendre et à effectuer qui existe. Cependant, il est vraiment très lent et complètement inefficace lorsqu'il doit trier beaucoup de données. Cet algorithme fonctionne de la manière suivante : on commence par dire que la 1ère valeur de la liste de nombre correspond à la valeur minimale, et on compare la valeur minimale aux autres valeurs. Si une valeur est inférieure à la valeur minimale, celle-ci est remplacée par la valeur trouvée et les comparaisons se font à partir de la nouvelle valeur minimale. Une fois toutes les valeurs comparées, on déplace la dernière valeur minimale trouvée devant la 1ère valeur de la liste. Il ne reste plus qu'à répéter cette méthode en ne partant plus de la 1ère valeur, mais de la 2e, puis 3e, puis 4e... valeur, jusqu'à l'avant dernière valeur de la liste. Voici la fonction qui permettrait de faire cela :

def tri_selection(list):
    for i in range(len(list)):
        mini = i
        for j in range(i, len(list)):
            if list[j] < list[mini]:
                mini = j
        list[i], list[mini] = list[mini], list[i]
    return list

Le tri rapide ou Quick Sort

Le tri rapide est un autre algorithme de tri, basé sur la récursivité, qui est très utilisé pour sa relative simplicité et sa rapidité. Il consiste à choisir un nombre de la liste au hasard, que l'on appelle nombre pivot, et auquel on compare les autres valeurs de la liste. Si la valeur comparée est inférieure au nombre pivot, on la place dans une liste que l'on nomme "inferieure" par exemple, sinon on la place dans une liste "superieur". Une fois toutes les valeurs comparées, on obtient normalement 2 listes : la liste "inferieur" contenant toutes les valeurs inférieurs au pivot et la liste "supérieur" contenant toutes celles supérieures. Il ne reste plus qu'à répéter cette méthode pour les 2 listes, jusqu'à ce que celles-ci ne contiennent plus qu'une seule valeur.

def tri_rapide(list):
    inferieur = []; pivot = []; superieur = []
    if len(list) < 2:
        return list
    pivotNombre = random.choice(list)
    for i in list:
        if i < pivotNombre:
            inferieur.append(i)
        elif i > pivotNombre:
            superieur.append(i)
        else:
            pivot.append(i)
    return tri_rapide(inferieur) + pivot + tri_rapide(superieur)

Comparaison des algorithmes

Lorsque l'on teste les deux algorithmes de tri, l'on se rend compte que la différence majeure se trouve au niveau du temps d'exécution : le tri rapide est beaucoup plus rapide que le tri par sélection. Pour mieux s'en rendre compte, regardez le tableau suivant :

Nous pouvons voir que plus il y a de nombres à trier, et plus la différence de temps d'exécution entre les deux algorithmes est grande. Cette différence de temps est d'autant plus importante que des chercheurs estiment que 1/4 des opérations effectuées par un ordinateur visent à trier des données. Imaginez que votre ordinateur trie ses données avec le tri par minimums successifs, vous voyez quelle serait sa lenteur.

Maintenant, à quoi cette différence de temps est dûe ? Elle est tout simplement dûe au nombre de comparaison effectuée : plus le programme doit comparer de nombres et plus il va prendre de temps. Pour vérifier, tester à la main les deux algorithmes de tri sur la liste de nombres suivante et comptez le nombre de test que vous devez faire pour la trier :

Normalement, vous devriez obtenir 21 tests pour le tri par sélection et entre 10 et 21 pour le tri rapide, tout dépend du nombre pivot que vous avez choisi à chaque fois.

A noter que la probabilité d'obtenir 10 comparaisons est beaucoup plus grande que celle d'en obtenir 21, car dans le premier cas, il faudrait avoir 3 fois la chance de tomber sur le meilleur nombre pivot possible, alors que dans le second, il faudrait avoir 7 fois la chance de tomber, cette fois-ci, sur le pire nombre pivot possible. A noter aussi que plus on a de nombres à trier et plus la différence entre le nombre de comparaisons effectuées par chaque algorithme est grande.

La récursivité : inutile dans d'autres cas

Si les fonctions récursives sont très pratiques pour trier des données, ce n'est pas toujours le cas dans d'autres programes. C'est ce que nous allons voir à travers un programme permettant de calculer la factorielle d'un nombre et un autre permettant de calculer les nombres présents dans le triangle de Pascal. Toute fois, si la partie précédente nécessitait quelques explications, le principe de la récursivité restant toujours le même, la partie suivante sera moins détaillée.

La factorielle d'un nombre

La factorielle d'un nombre \(n\) correspond au produit des nombres entiers positifs strictement à \(n\), ce qui revient à écrire :

$$n! = n\times(n-1)\times(n-2)\times...\times2$$

Par exemple :

$$5! = 5\times4\times3\times2 = 120$$

Le programme consiste à afficher la factorielle d'un nombre entré par l'utilisateur, que l'on peut calculer de deux façons différentes. La première en utilisant la récursivité :

def recursivite(nb):
    if nb > 2:
        return nb * recursivite(nb - 1)
    return nb

La seconde en mettant une simple boucle pour dans la fonction :

def boucle(nb):
    for i in range(2, nb):
        nb *= i
    return nb

Notez que, en Python, \(range(2,nb)\) correspond à l'intervalle \([2; nb[\).

Le triangle de Pascal

Pour ceux qui ne savent pas ce qu'est le triangle de Pascal, regardez l'image suivante :

Ce triangle, inventé par le mathématicien Blaise Pascal (1623 - 1662), permet de calculer facilement les identités remarquables \((a+b)^{n}\) et \((a-b)^{n}\) car ses nombres correspondent aux coefficients et aux puissances du résultat. Ce triangle est, par ailleurs, très facile à retrouver car chaque nombre correspond à la somme du nombre se trouvant à la colonne - 1 et ligne - 1 et du nombre se trouvant à la colonne et ligne - 1.

Un petit exemple : le nombre se trouvant à l'intersection de la ligne 5 et de la colonne 3, soit 10, est égal à la somme du nombre se trouvant à l'intersection de la ligne 4 et de la colonne 2, soit 4, et du nombre se trouvant à l'intersection de la ligne 4 et de la colonne 3, soit 6. Ainsi, grâce à ce triangle, on sait facilement que :

$$(a+b)^{4}=a^{4} + 4a^{3}b + 6a^{2}b^{2} + 4ab^{3} + b^{4}$$

Maintenant, passons au programme. Le but de celui-ci est d'afficher le nombre correspondant à une ligne et une colonne entrées par l'utilisateur. Par exemple, si l'on demande le nombre se trouvant à la ligne 4 et à la colonne 3, le programme affiche le nombre 6. Pour se faire, nous allons utiliser 2 algorithmes différents.

Le premier fait appel à la récursivité ce qui donne le code suivant :

def recursivite(ligne, colonne):
    if colonne == 0 or colonne == ligne:
        return 1
    return recursivite(ligne - 1, colonne - 1) + recursivite(ligne - 1, colonne)

Le second, quant à lui, utilise une simple boucle pour, et dans ce cas-là, c'est amplement suffisant.

def boucle(ligne, colonne):
    c = 1;
    for x in range(0, colonne):
        c *= (ligne - x) / (x + 1)
    return int(round(c))

Comparaison des algorithmes

Comme pour les deux algorithmes de tri, comparons de nouveau les temps d'exécution des différents algorithmes du triangle de Pascal et de la factorielle. Cette fois-ci, nous nous rendons compte que, dans les deux cas, les algorithmes les plus lents sont ceux qui utilisent la récursivité. Voici encore deux petits tableaux, le premier pour la factorielle et le second pour le triangle de Pascal, qui mettent en évidence ces différences de temps :

Dans la sous-partie précédente, nous avions vu pourquoi la récursivité était plus rapide, maintenant voyons pourquoi, pour le triangle de Pascal et la factorielle, elle est plus lente. Pour cela, regardez l'image suivante :

Nous voyons que la fonction factorielle est appelée tant que celle-ci n'a pas pour paramètre 1. Lorsque celle-ci a pour paramètre 1, elle connaît donc tous les nombres nécessaires à calculer la factorielle. Elle peut donc repartir dans le sens contraire et faire le calcul petit à petit. Elle met donc forcément plus de temps pour retourner le résultat qu'une simple boucle pour car cette dernière n'aura pas besoin de chercher les nombres nécessaires à la multiplication.

Utiliser la récursivité dans ces deux derniers cas-là n'a alors pas beaucoup d'intérêt.

En conclusion, la récursivité est un outil qui peut être très puissant dans un programme. Cependant, ce n'est pas une raison pour l'utiliser dans n'importe quel cas. Dites vous que la récursivité n'est à utiliser que si elle ne peut pas être remplacée par une boucle pour.