Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Chapitre 05 - Récursivité. Paradigme « diviser pour régner »

Récursivité

On va dans cette partie présenter le concept simple mais néanmoins profond de récursivité, qui est très proche de la notion mathématique de récurrence.

Principe

Commençons par une définition : un sous–programme (procédure ou fonction) est dit récursif s’il s’appelle lui-même.

[Note]

Le mot récursif provient du latin recurrere signifiant courir en arrière. Le lecteur comprendra vite pourquoi ce terme est bien choisi.

L'idée sous-jacente est que pour résoudre un problème ou effectuer un calcul, on se ramène à la résolution d’un problème similaire mais de complexité moindre. On recommence ainsi jusqu’à obtenir un problème élémentaire que l'on sait résoudre.

Pour cela, le sous-programme en question va s'appeler lui-même avec un paramètre plus "petit". Cet appel en induira un autre, puis un autre, etc. D'appel en appel, la taille du paramètre va ainsi diminuer. On s'arrêtera quand cette taille sera celle d'un problème immédiatement résolvable.

Les différents problèmes intermédiaires, ceux permettant de passer du problème initial au problème élémentaire, sont stockés successivement en mémoire dans ce que l'on appelle une pile. Il s'agit d'une structure de données dans laquelle on accède aux éléments dans l'ordre inverse de leur ajout en mémoire. Dans notre cas, on utilisera ainsi en premier le résultat du problème élémentaire, puis de proche en proche on arrivera à celui du problème initial.

Example 1.1. Implémentation récursive de la fonction factorielle

Rappelons tout d'abord que n ! = 1 × 2 × 3 × ... × n . On montre alors facilement la relation de récurrence n ! = n × ( n - 1 ) ! Si l'on sait calculer ( n - 1 ) ! on connaîtra donc la valeur de n ! Or, toujours d'après la formule de récurrence, ( n - 1 ) ! = ( n - 1 ) × ( n - 2 ) ! On est donc ramené au calcul de ( n - 2 ) ! Et ainsi de suite jusqu'à 1 ! dont on connaît la valeur : 1.

Voici maintenant la fonction Python qui utilise cette formule de récurrence pour calculer récursivement la valeur de n ! :

def factorielleRecursive(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n*factorielleRecursive(n-1)

Voyons comment s'exécute cette fonction avec par exemple n = 4 :

Comme expliqué précédemment, les différents appels récursifs sont empilés en mémoire jusqu’à ce que le paramètre d’appel vaille 1 (condition d’arrêt). Ils sont ensuite dépilés jusqu’à l’appel initial.


[Warning]

Il est indispensable de prévoir une condition d’arrêt à la récursion sinon le sous-programme va s'appeler une infinité de fois.

Example 1.2. Une erreur à ne pas commettre

On a omis ici la condition d'arrêt, cette fonction ne se terminera en théorie donc jamais :

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

En pratique, la pile où sont stockés les appels récursifs étant de taille finie, une fois qu'elle sera pleine le programme ne répondra plus.


Récursivité versus itération

Par opposition, on qualifiera d'itératif un sous-programme qui ne s'appelle pas

On peut démontrer qu'il est toujours possible de transformer un algorithme récursif en un algorithme itératif et inversement.

L’algorithme itératif sera plus rapide une fois implémenté dans un langage de programmation mais souvent plus complexe à écrire.

Example 1.3. Implémentation itérative de la fonction factorielle

Cette fois ci on utilise une structure itérative pour effectuer le calcul :

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

[Note]

Il est manifeste que cette version est beaucoup moins élégante que la précédente.

Evoquons à présent quelques arguments en faveur puis en défaveur de l'usage de la récursivité.

Comme nous l'avons déjà mentionné, cette technique de programmation est très élégante et lisible. Elle évite en effet souvent le recours à de nombreuses structures itératives. Elle est d'autre part très utile voire indispensable pour concevoir des algorithmes sur des structures de données complexes comme les listes, les arbres et les graphes.

[Note]

Nous reviendrons sur ces différentes structures de données dans les cours de théorie des graphes 2GRA et d'algorithmique avancée 2ADS.

L'inconvénient majeur de la récursivité est qu'une fois cette technique implémentée dans un langage de programmation, elle est très "gourmande" en mémoire. Rappelons en effet que l’on doit empiler tous les appels récursifs. Des débordements de capacité peuvent donc se produire s'il arrive que cette pile soit pleine.

[Note]

Le lecteur pourra par exemple essayer de calculer 1000 ! avec la version récursive de la fonction factorielle.

En Python, on peut toutefois ajuster manuellement la taille de la pile dédiée aux appels récursifs grâce à la fonction setrecursionlimit. Mais il y a cependant une taille limite à ne pas dépasser.

[Note]

Lors du cours 2ADS, on apprendra à implémenter de façon plus satisfaisante des sous-programmes récursifs afin entre autres d'être beaucoup moins dépendant de la dimension de cette pile. Il s'agit d'une technique appelée programmation dynamique.

Récursivité croisée

Il s'agit d'un cas bien particulier de récursivité où un sous-programme appelle un autre sous-programme qui lui-même appelle le premier.

Example 1.4. Test de la parité d'un nombre

Il est clair qu'un nombre n est pair si et seulement si n - 1 est impair. De même un nombre n est impair si et seulement si n - 1 est pair. De plus 0 est un nombre pair.

Ces remarques conduisent à cette situation de récursivité croisée :

def pair(n):
    if n == 0:
        return True
    else:
        return impair(n-1)

def impair(n):
    if n == 0:
        return False
    else:
        return pair(n-1)

[Note]

Il y a évidemment bien plus simple pour tester la parité d’un nombre... En regardant par exemple si le reste de la division par 2 de ce nombre est égal à 0 ou non.

Figure 1.1. "Drawing hands" de Maurits Cornelis Escher

Une petite minute culturelle, avec cette célèbre lithographie pouvant illustrer le concept de récursivité croisée :

"Drawing hands" de Maurits Cornelis Escher

Récursivité multiple

Lorsqu'un sous-programme récursif réalise plusieurs appels à lui même, on parle de récursivité multiple.

Example 1.5. Calcul des coefficients binomiaux

Rappelons tout d'abord la définition d'un coefficient binomial : pour n et k avec 0 k n , on a

( n k ) = { 1 si k = 0 ou si k = n ( n 1 k 1 ) + ( n 1 k ) sinon

La fonction récursive implémentant cette relation de récurrence réalisera donc deux appels à elle-même :

def coeffs(n,k):
    if k == 0 or k == n:
        return 1
    else:
        return coeffs(n-1,k-1) + coeffs(n-1,k)

[Note]

Cette formule de récurrence permet également la construction du très célèbre triangle de Pascal. Voir cours 1SET à ce sujet.

Récursivité imbriquée

Lorsqu'un sous-programme récursif dont l’appel à lui même contient un autre appel à lui même, on parle de récursivité imbriquée.

Example 1.6. La fonction 91 de McCarthy

Cette fonction est définie sur par

f ( n ) = { n 10 si n > 100 f ( f ( n + 11 ) ) si n 100

On obtient donc une fonction dont l'appel récursif contient un autre appel récursif :

def f91(n):
    if n > 100:
        return n-10
    else:
        return f91(f91(n+11))

[Note]

Cette fonction est certes anectodique mais son auteur ne l'est pas. John McCarthy (1927-2011) fut en effet l'un des fondateurs de l'intelligence artificielle moderne. Il a en particulier créé le langage LISP, voir cours 3AIT à ce sujet.

Exercice

On propose ici au lecteur un petit exercice d'application immédiate afin qu'il puisse tester sa bonne compréhension de ce qui précède.

Exercice corrigé : fonction puissance

1.1.

Ecrire de deux façons, itérative et récursive, une fonction ayant pour paramètres un réel x et un entier n, et retournant la valeur de x n .

Version itérative : on initialise une variable à 1, et à chaque itération on la multiplie par x. On obtient donc finalement x × x × ... × x = x n .

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

Version récursive : on utilise la formule de récurrence x n = x × x n - 1 et la condition d'arrêt x 0 = 1 .

def puissanceRecursive(x,n):
    if n == 0:
        return 1
    else:
        return x*puissanceRecursive(x,n-1)
[Note]

Cette fonction puissance existe bien sûr nativement en Python, mais lorsque l’on apprend il faut parfois réinventer la roue. Mais ça le lecteur le sait déjà.

[Note]

Retenir au passage cette technique pour calculer un produit : initialiser une variable à 1 et à chaque itération la multiplier par le terme voulu.

Paradigme "diviser pour régner"

On va présenter dans cette partie un paradigme de programmation basé sur la notion de récursivité.

Principe

Les algorithmes de la partie précédente étaient basés pour la plupart sur la simple exploitation d’une formule de récurrence.

Mais beaucoup de problèmes plus complexes se résolvent aussi naturellement de façon récursive, avec des algorithmes s’appellant eux-mêmes une ou plusieurs fois sur des données de tailles inférieures. Et ce jusqu'à obtenir des problèmes de taille élémentaire, résolvables immédiatement. Il faudra enfin combiner les résultats issus de chacun de ces appels.

Cette méthode dite "diviser pour régner" se décompose ainsi en trois phases :

  1. Diviser : on divise les données initiales en plusieurs sous-parties.

  2. Régner : on résout récursivement chacun des sous-problèmes associés (ou on les résout directement si leur taille est assez petite).

  3. Combiner : on combine les différents résultats obtenus pour obtenir une solution au problème initial.

Cela va prendre tout son sens sur les exemples à venir, qui vont nous permettre de nous familiariser avec ce principe général.

Pour chacun d’eux on présentera en détail les trois phases : diviser, régner et combiner.

Premier exemple : calcul du maximum d'une liste

Le problème est de calculer le maximum d'une liste de nombres.

En adoptant le paradigme "diviser pour régner", l'idée pour résoudre cette question est de calculer récursivement le maximum de la première moitié de la liste et celui de la seconde, puis de les comparer. Le plus grand des deux sera le maximum de toute la liste. La condition d'arrêt à la récursivité sera l'obtention d'une liste à un seul élément, son maximum étant bien sûr la valeur de cet élément.

Voici donc les trois étapes de la résolution de ce problème via la méthode "diviser pour régner" :

  1. Diviser la liste en deux sous-listes en la “coupant” par la moitié.

  2. Calculer récursivement le maximum de chacune de ces sous-listes. Arrêter la récursion lorsque les listes n'ont plus qu'un seul élément.

  3. Retourner le plus grand des deux maximums précédents.

Présentons maintenant cet algorithme implémenté en Python :

def maximum(l,d,f):
    if d == f:
        return l[d]
    m = (d+f) // 2
    x = maximum(l,d,m)
    y = maximum(l,m+1,f)
    return x if x > y else y
[Note]

On pouvait bien sûr utiliser un test avec alternative à la place de l’opérateur ternaire.

Les notations utilisées sont naturelles, "d" comme "début", "m" comme "milieu", et "f" comme "fin".

[Note]

Pour rappel, une version itérative résolvant ce problème a été implémentée lors de la séance d'exercices du chapitre 4.

Second exemple : recherche d'un élément dans une liste

Le problème est de rechercher la présence d’un élement dans une liste.

En adoptant le paradigme "diviser pour régner", l'idée pour résoudre cette question est de rechercher récursivement l'élément dans la première moitié de la liste et dans la seconde, puis de combiner les résultats via l'opérateur logique or. En effet, l'élément recherché sera dans la liste s'il est dans la première moitié ou dans la seconde. La condition d'arrêt à la récursivité sera l'obtention d'une liste à un seul élément, car il est alors immédiat de conclure si l'élément recherché appartient à une telle liste ou non.

Voici donc les trois étapes de la résolution de ce problème via la méthode "diviser pour régner" :

  1. Diviser la liste en deux sous-listes en la “coupant” par la moitié.

  2. Rechercher la présence de l’élément dans chacune de ces sous-listes. Arrêter la récursion lorsque les listes n'ont plus qu'un seul élément.

  3. Combiner avec l'opérateur logique or les résultats obtenus.

Présentons maintenant cet algorithme implémenté en Python :

def recherche(l,x,d,f):
    if d == f:
        return l[d] == x
    m = (d+f) // 2
    return recherche(l,x,d,m) or recherche(l,x,m+1,f)
[Note]

Pour rappel, une version itérative résolvant ce problème a été implémentée lors de la séance d'exercices du chapitre 4.

Troisième exemple : recherche d'un élément dans une liste triée

Le problème est de rechercher la présence d’un élement dans une liste préalablement triée.

L'idée pour résoudre cette question est d'utiliser une méthode dichotomique. La liste étant triée, après comparaison avec l’élément du "mileu" il est en effet facile de voir dans quelle moitié peut éventuellement se trouver l’élément cherché. On aura plus alors qu'à recommencer récursivement la recherche.

[Note]

Le terme dichotomie provient du grec ancien "dikhotomia", signifiant "division en deux parties".

En mathématiques et algorithmique il s'agit d'une technique classique.

Example 1.7. Réduction de la recherche à une seule moitié de la liste

Recherchons l'élement - 4 dans cette liste triée :

La valeur - 4 étant plus petite que la valeur centrale 3, on va donc continuer la recherche uniquement dans la première moitié de la liste.


[Note]

Cette technique ne fonctionne bien sûr pas pour des listes non triées.

Là encore la condition d'arrêt à la récursivité sera l'obtention d'une liste à un seul élément.

Voici donc les trois étapes de la résolution de ce problème via la méthode "diviser pour régner"

  1. Diviser la liste en deux sous-listes de même taille (à un élément près) en la "coupant" par la moitié.

  2. Rechercher récursivement la présence de l’élément recherché dans la “bonne” des deux sous-listes après l'avoir comparé à l'élément situé au milieu de la liste.

  3. Pas de résultats à combiner puisque l’on ne “travaille” que sur l'une des deux sous-listes.

Présentons maintenant cet algorithme implémenté en Python :

def dicho(l,x,d,f):
    if d > f:
        return False
    else:
        m = (d+f) // 2
        if l[m] == x:
            return True
        else:
            if x < l[m]:
                return dicho(l,x,d,m-1)
            else:
                return dicho(l,x,m+1,f)

En voici une seconde version qui utilise certaines spécificités du Python :

def dicho2(l,x):
    if len(l) == 0:
        return False
    else:
        m = (len(l)-1) // 2
        if l[m] == x:
            return True
        else:
            if x < l[m]:
                return dicho2(l[:m],x)
            else:
                return dicho2(l[m+1:],x)
[Note]

Cette deuxième version est donc moins portable que la précédente. Elle est de plus moins rapide et moins optimale, car à chaque appel récursif on effectue une copie partielle de la liste.

Sans rentrer dans les détails, on voit facilement que l'algorithme de recherche par dichotomie est moins gourmand en nombre d’opérations que celui présenté dans la sous-partie précédente.

Pour la première méthode, si un élément n’appartient pas à une liste de n éléments il faudra n comparaisons pour le détecter. En effet, tous les éléments de la liste seront testés un par un.

Alors qu'avec une recherche dichotomique il faudra seulement effectuer environ log ( n ) comparaisons.

Example 1.8. En "peu" de comparaisons on conclut sur la présence ou non d'un élément

Après trois comparaisons, on constate que l'élément - 4 n'appartient pas à cette liste :

En effet, après avoir comparé - 4 à la valeur du milieu 3, on continue la recherche dans la première moitié de la liste. On compare alors - 4 avec l'élément central de cette première moitié, à savoir - 1 . On recommence de nouveau avec cette fois une liste réduite à l'élément - 5 . On conclut alors que - 4 est absent de cette liste. On a donc effectué trois comparaisons pour conclure à l'absence d'un élément dans une liste à sept éléments.


Le lecteur est en droit de se demander pourquoi le nombre de comparaisons est au pire environ égal à log ( n ) . Par "au pire" on entend "si l'on ne trouve pas l'élément recherché". Voici quelques éléments de réponse. Imaginons que notre liste possède exactement n = 2 k éléments. Puisque l'on coupe la liste en deux à chaque appel récursif, après la première comparaison on ne considèrera plus que 2 k - 1 éléments, après la seconde 2 k - 2 , etc. Après k comparaisons on aboutira ainsi à une liste à 1 élément. Il faudra donc au total k + 1 comparaisons pour conclure à l'absence d'un élément. Or puisque n = 2 k , on a k = log 2 ( n ) . Ce qui prouve notre résultat dans le cas de listes dont le nombre d'éléments est une puissance de 2. Si ce n'est pas le cas, on encadre le nombre d'éléments entre deux puissance de 2, et l'on conclut sans problèmes.

La recherche dichotomique est donc plus efficace, mais elle requiert cependant que notre liste de données soit triée.

[Note]

L'étude de plusieurs algorithmes de tri fera l'objet du prochain chapitre de cours.

[Note]

La comparaison de l’efficacité de plusieurs algorithmes résolvant le même problème est le sujet de la théorie de la complexité. Cette question sera abordée dans le cours d'Algorithmique avancée 2ADS.

Quatrième exemple : algorithme de Karatsuba

Le problème est de multiplier deux entiers par une méthode plus rapide que celle usuelle.

Voyons déjà pourquoi la méthode traditionnelle, celle enseignée sur les bancs de l'école, n'est pas optimale.

Imaginons par exemple que l’on veuille effectuer le produit 12 × 34 . Utilisons la technique habituelle qui consiste à "poser" l'opération :

On a alors effectué quatre "petits" produits : 4 × 2 , 4 × 1 , 3 × 2 , et 3 × 1 .

Réécrivons maintenant ce calcul sous cette forme

12 × 34 = ( 1 × 10 + 2 ) × ( 3 × 10 + 4 ) = 3 × 10 2 + ( 1 × 4 + 2 × 3 ) × 10 + 8 = 300 + 100 + 8 = 408

Et généralisons le à tout produit de nombres à deux chiffres

a b × c d = ( a × 10 + b ) × ( c × 10 + d ) = a × c × 10 2 + ( a × d + b × c ) × 10 + b × d

Or

( a + b ) × ( c + d ) = a × c + b × d + a × d + b × c

On a donc

a × d + b × c = ( a + b ) × ( c + d ) a × c b × d

Finalement, le produit recherché peut s'écrire sous cette forme

a b × c d = a × c × 10 2 + ( ( a + b ) × ( c + d ) a × c b × d ) × 10 + b × d

On s'aperçoit alors qu’il suffit en fait de réaliser trois “petits” produits contre quatre dans la méthode usuelle.

De plus, ce que l’on vient de faire sur des nombres à 2 chiffres on peut bien sûr le faire sur des nombres à n chiffres, en les coupant en deux parties de n / 2 chiffres

( a × 10 n 2 + b ) × ( c × 10 n 2 + d ) = a × c × 10 n + ( a × d + b × c ) × 10 n 2 + b × d

Là encore, on utilisera le calcul

a × d + b × c = ( a + b ) × ( c + d ) a × c b × d

Présentons maintenant l'algorithme de multiplication tirant parti des constatations précédentes :

  1. Séparer chaque nombre en deux parties de n / 2 chiffres où n est le nombre de chiffres du plus grand des deux

    x = a × 10 n 2 + b et y = c × 10 n 2 + d
  2. Effectuer les trois produits : a × c , b × d , ( a + b ) × ( c + d )

  3. Combiner les résultats obtenus.

[Note]

Cet algorithme est dû au mathématicien russe Anatolii Alexevich Karatsuba (1937–2008).

En voici une implémentation en Python en utilisant les opérateurs **, // et % :

def karatsuba(x,y):
    if x < 10 or y < 10:
        return x*y
    m = max([len(str(x)),len(str(y))])
    n = (m+1)//2
    z = 10**n
    a, b = x//z, x%z
    c, d = y//z, y%z
    u = karatsuba(a,c)
    v = karatsuba(a+b,c+d)
    w = karatsuba(b,d)
    return u*(10**(2*n))+(v-u-w)*(10**n)+ w
[Note]

On proposera lors de la séance d'exercices une version de cet algorithme ne requérant pas l'usage de ces opérateurs **, // et %. Elle sera certes plus complexe à écrire, mais sera aussi plus optimale. En effet, sous couvert d'une simplicité apparente, // et % réalisent en fait des divisions assez couteuses.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels