Question 149

A quoi sert la récursivité? Comment écrire une fonction récursive en VB?

Principes

Principe simplifié : Une fonction est dite récursive si elle s'appelle elle même.

Dans quels cas, dans quel contexte? D'une façon générale, l'approche récursive permet de fractionner un gros problème en un problème plus petit; En d'autres mots, on traite "une partie" puis on se rappelle pour traiter les autres "parties", jusqu'à avoir traité "le tout".

Diviser pour gagner

Les algorithmes de type "Diviser pour vaincre" ("divide and conquer" en anglais) font très souvent appel à la récursivité. L'algorithme de tri "Quick Sort" ou "Tri Rapide" en est une parfaite illustration : on divise le gros tableau à trier en petits tableaux, jusqu'à n'avoir plus que des tableaux de 2 éléments; à ce stade, le tri devient évident.

La récursivité est une notion très importante en informatique, car cette technique peut permettre de résoudre en peu de lignes de code des problèmes complexes, qui seraient difficiles ou longs à traiter autrement.

Et VB dans tout ça? La suite de cet article montre avec quelques exemples comme il est simple de coder une fonction récursive en VB.

Exemples d'usage

On reconnaît souvent simplement une définition récursive. Il suffit d'identifier dans la description du problème une "auto-référence" au problème.
La fonction factorielle
La classique fonction mathématique "Factorielle" qui peut se définir de 2 façons (parfaitement équivalentes) :
- La définition "classique" (itérative) :
    Factorielle(n) = n * (n-1) * (n-2) * ... * 3 * 2 * 1

- La définition récursive :
    Factorielle(1) = 1
    Factorielle(n) = n * Factorielle(n-1)

Il est facile d'écrire une fonction récursive avec Visual Basic, très naturellement. Voici par exemple une implémentation possible de la fonction factorielle :

Function Factorielle(ByVal n As Long) As Long

    If n <= 1 Then
        Factorielle = 1
    Else
        Factorielle = n * Factorielle(n - 1)
    End If
End Function

On voit clairement que la fonction s'appelle elle même; dans cet exemple, l'implémentation est très proche de la définition mathématique, c'est même la traduction "mot à mot" en basic de la définition. En outre, cette façon d'implémenter la fonction est très naturelle. Note : on verra plus loin que dans ce cas, faire une implémentation récursive ne serait pas une bonne idée dans un vrai programme.

L'implémentation donnée ici est dite "récursive non terminale", par opposition à "récursive terminale". Une fonction est dite récursive terminale si la valeur retournée est une valeur fixe ou une valeur directement calculée par la fonction elle même. En d'autre mots, une fonction est récursive terminale si l'appel récursif est la dernière chose faite par la fonction.
Voici une implémentation "récursive terminale" de la même fonction factorielle :

Private Function Fact2(ByVal n As Long, ByRef cumul As Long) As Long

    If n <= 1 Then
        Fact2 = cumul
    Else
        Fact2 = Fact2(n - 1, cumul * n)
    End If
End Function

Le principe sous-jacent ici est de faire les calculs dans un "accumulateur interne". Les fonctions récursives terminales sont plus efficaces que les fonctions récursives non terminales, car elles sont équivalentes à une écriture strictement itérative.
On peut si on le souhaite "masquer" l'utilisation de l'accumulateur, en écrivant une fonction de plus haut niveau qui fait appel à cette fonction (wrapper) :

Private Function Fact2_Wrap(ByVal n As Long) As Long
     
    Fact2_Wrap = Fact2(n, 1)
End Function

Exemple de mise en oeuvre : Ecrire une fonction qui inverse une chaîne de caractères.
On peut remarquer qu'inverser une chaîne, c'est prendre le dernier caractère, et le concaténer avec l'inversion de la chaîne privée du dernier caractère. On reconnaît bien là une auto-référence, un fractionnement du problème en un problème plus petit. Ceci donnerait :
Inv("ABCDEF") => F & Inv("ABCDE") => F & E & Inv("ABCD") => F & E & D & Inv("ABC") => etc.

Voici une traduction littérale :

Private Function ReverseString(ByVal s As String) As String
    Dim l As Long

    l = Len(s)
    If l <= 1 Then
        ReverseString = s
    Else
        ReverseString = Mid$(s, l, 1) & ReverseString(Mid$(s, 1, l - 1))
    End If
     
End Function

Une fois de plus, on remarque que l'écriture récursive est très "naturelle" : l'implémentation est très proche de l'énoncé "en français" du problème à résoudre. De plus, les implémentations récursives ont un coté un peu magique. Au premier coup d'oeil, on ne saisit pas forcément tout de suite ce que la fonction doit faire. On remarque aussi que les fonctions récursives sont souvent très courtes : on a bien fractionné le gros problème de départ en tout petits problèmes, à la résolution simple.

Quelques exemples classiques d'usage de fonctions ou algorithmes récursifs : parcours de répertoires, recherche de chemin dans un labyrinthe ou dans un graphe, parcours d'arbres, résolution de problèmes ("Tours De Hanoï", ...), etc.

Attention à la pile!

A noter tout de même que l'emploi de la récursivité ne doit se faire qu'à bon escient et avec précautions. Même si c'est parfois une solution rapide et élégante, ce n'est pas toujours la solution la plus efficace.
Le problème le plus fréquent que l'on rencontre lors de la mise au point de procédures ou fonctions récursives est le "Out of stack space" (erreur de saturation de pile). Ceci est toujours du à une mauvaise condition de sortie : la fonction s'appelle elle même "à l'infini", jusqu'à avoir consommé tout l'espace de la pile d'appel. En effet, un algorithme récursif a pour effet d'empiler les appels de fonction, pouvant conduire à un "plantage" brutal du programme si il vient à consommer toute la mémoire disponible pour la gestion de la pile d'appel.

Enfin, un algorithme récursif peut s'avérer avoir des performances très mauvaises. Par exemple, l'implémentation récursive (non terminale) de la factorielle est terriblement peu efficace comparée à la classique implémentation itérative!

En savoir plus

Voir aussi :
Date de publication : 25 février 2007
Dernière modification : 25 février 2007
Rubriques : Algorithmique
Mots-clés : récursif, récursive, récursivité, fonction, fonctions