VBA Excel - Initiation à la récursivité

Introduction

Cette fiche pratique est loin d'être exhaustive sur le sujet. Il s'agit de présenter la récursivité par des fonctions simples. Une initiation par quelques exemples aisés en somme...
Une fonction (ou une procédure) est dite récursive lorsqu'elle s'appelle elle-même. Elle a besoin d'une porte de sortie, communément appelée point d'arrêt. Celui-ci consiste en une instruction qui indique que le reste de la procédure ne doit plus être exécuté.
Conscient que cette théorie demeure relativement complexe, passons tout de suite au premier exemple.

Factorielle

Analyse

En mathématiques, la factorielle d'un entier naturel n, noté n!, est le produit des nombres entiers strictement positifs inférieurs ou égaux à n (sources wikipédia). Cela se traduit donc simplement par : n! = n x (n-1) x (n-2) x (n-3) x... x 1. On peut également adopter une autre écriture mathématique pour cette équation, factorielle n étant égal à n multiplié par la factorielle de n-1 : n! = n x (n-1)!
On voit, dans cette dernière équation, se dessiner notre récursivité. Factorielle(n) = n * Factorielle(n-1). Nous avons bien là une fonction qui s'appelle elle-même.
Quel en est la porte de sortie, le « point d'arrêt » ? Dans la définition même de Factorielle, nous la trouvons : le produit des nombres entiers strictement positifs. Soit un point d'arrêt lorsque notre n-? = 1.

Le code

Function Factorielle(Nb As Integer)
' Le If est là pour le point d'arrêt, afin de ne plus exécuter le reste de la procédure
If Nb = 1 Then ' ===> Point d'arrêt : nous sommes arrivés à 1
    Factorielle = 1
Else
    Factorielle = Nb * Factorielle(Nb - 1) ' ===> Equation : Factorielle(n) = n * Factorielle(n-1)
End If
End Function

PGCD

Algorithme d'Euclide

En mathématiques

Pour déterminer le PGCD de deux nombres a et b, il nous faut effectuer la division de a par b (on trouve alors un reste r1) puis la division de b par r1 (on note le reste trouvé r2), puis celle de r1 par r2... Et ainsi de suite. La définition de la division euclidienne assure que la suite r1, r2... est strictement décroissante et finira par s'annuler. Le PGCD de a et b est le dernier reste non nul de cette suite (sources wikipédia).

En informatique

Iil nous faut donc une fonction à laquelle nous allons passer deux paramètres (nos deux nombres initiaux). Cette fonction va calculer le reste de la division de ces deux nombres, et s'appeler elle-même en utilisant le reste de cette division comme second paramètre. Le point d'arrêt de cette fonction étant, bien entendu, lorsque le reste de la division sera nul.

Le code

Function PGCD_Recursif(Nb1 As Long, Nb2 As Long)
Dim Reste As Long
Reste = Nb1 Mod Nb2 ' ===> Division et calcul du reste
If Reste = 0 Then ' ===> Point d'arrêt
    PGCD_Recursif = Nb2 ' ===> Nb2 est le dernier reste non nul
Else
    PGCD_Recursif = PGCD_Recursif(Nb2, Reste) ' ===>Appel récursif
End If
End Function 

Le code d'appel

Il est également dit, dans la définition, que le calcul du PGCD de 2 nombres Nb1 et Nb2 nécessite que :

• Nb1>Nb2
• Nb1 et Nb2 différents de 0

Pour cela, il suffit d'ajouter deux petits tests dans la fonction d'appel. Le premier va intervertir les deux nombres si Nb2>Nb1, le second va résoudre le cas d'un des deux (ou les deux) nombres nuls.

Sub Appel_PGCD() 
Dim Nbre1 As Long, Nbre2 As Long, NbreTemp As Long
'cas d'un des deux nombre égal à zéro
If Nbre1 = 0 Then MsgBox "Le PGCD est égal à" & Nbre2: Exit Sub
If Nbre2 = 0 Then MsgBox "Le PGCD est égal à" & Nbre2: Exit Sub
'Nbre1 doit être supérieur à Nbre2
If Nbre1 < Nbre2 Then
    NbreTemp = Nbre1
    Nbre1 = Nbre2
    Nbre2 = NbreTemp
End If
MsgBox PGCD_Recursif(Nbre1, Nbre2) 'Lancement Function PGCD_Recursif
End Sub

Conversion de chiffres Romains

Analyse

La numérotation des nombres Romains a été normalisée dans l'usage actuel et repose sur quatre principes :

• Toute lettre placée à la droite d'une autre figurant une valeur supérieure ou égale à la sienne s'ajoute à celle-ci.
• Toute lettre d'unité placée immédiatement à la gauche d'une lettre plus forte qu'elle, indique que le nombre qui lui correspond doit être retranché au nombre qui suit.
• Les valeurs sont groupées en ordre décroissant, sauf pour les valeurs à retrancher selon la règle précédente.
• La même lettre ne peut pas être employée quatre fois consécutivement sauf M.

(Sources)

Ici, nous n'allons pas nous atteler à la vérification du nombre Romain lui-même, par conséquent, les deux derniers principes ne nous intéressent pas. Nous allons juste convertir un nombre Romain en nombre arabe sans nous soucier si l'écriture du nombre romain est juste ou non.
Nous avons donc deux règles à vérifier :

• La valeur du premier chiffre est plus grande que celle du chiffre qui le suit. Dans ce cas, on ajoute, à la valeur du chiffre celle du reste.
• La valeur du premier chiffre est plus petite que celle du chiffre qui le suit. Dans ce cas, on converti le reste et on lui retranche la valeur du premier chiffre.

La récursivité tient ici dans la conversion du reste.
Le point d'arrêt de notre fonction réside dans la longueur de la chaîne composée par les chiffres romains. La conversion du dernier caractère (correspondant à la conversion du reste) sera, en effet, la conversion d'une chaîne de longueur égale à 1.
Il nous faudra deux fonctions, une récursive pour la conversion successive des valeurs et le calcul, et une pour évaluer la valeur de chacune des lettres composant le nombre romain.

Le code

Ne nous attardons pas sur la conversion des lettres en nombre arabe, elle ne comporte pas d'intérêt dans cette fiche pratique sur la récursivité...

Fonction de conversion de chacune des lettres

Function Conv(lettre As String) As Long
Dim Romains(), Arabes(), Pos As Integer

Romains = Array("M", "D", "C", "L", "X", "V", "I")
Arabes = Array(1000, 500, 100, 50, 10, 5, 1)
Pos = -1
On Error Resume Next
Pos = Application.Match(lettre, Romains, 0) - 1
On Error GoTo 0
If Pos <> -1 Then Conv = Arabes(Pos)
End Function

Fonction récursive

... de conversion de la chaîne de chiffres Romains :
Dans cette fonction, nous avons besoin de travailler sur la chaîne de caractères correspondante au nombre Romain. Il nous faut convertir lettre par lettre cette chaîne. Pour cela nous utiliserons la fonction Mid (voir l'aide en ligne). Il nous faut également « extraire » de cette chaine le « reste », soit une sous-chaîne débutant au nième caractère de la chaîne initiale et de longueur (longueur initiale - n). Mid nous permet également cela.

Function Converti(strRomain As String)
Dim i As Long, strLettr As String, Valeur As Integer

If Len(strRomain) = 1 Then ' ===> Point d'arrêt : la longueur de la chaine traitée (reste) = 1
    Converti = Conv(strRomain)
Else
    Valeur = Conv(Mid(strRomain, 1, 1)) ' ===> Appel de la fonction de conversion du chiffre
    ' Test de comparaison avec le chiffre Romain suivant
    ' pour toujours additionner, suffit de multiplier par -1 pour le cas ou le chiffre suivant est supérieur
    If Valeur < Conv(Mid(strRomain, 2, 1)) Then Valeur = Valeur * (-1) 
    ' Récursivité avec la chaîne de longueur réduite de 1
    Converti = Valeur + Converti(Mid(strRomain, 2, Len(strRomain) - 1))
End If
End Function

combinaisons d'une chaîne de caractères

Analyse

Supposons une chaîne de trois caractères : « aze » dont nous voulons, en retour, toutes les combinaisons possibles.
La liste des combinaisons s'obtient par la permutation de chacun des caractères.

• Première permutation avec la chaine abc
  • Le premier caractère va en bout de chaine : bca
  • le second va en bout de chaine : bac
• Deuxième permutation avec la chaine bca
  • Le premier caractère va en bout de chaine : cab
  • le second va en bout de chaine : cba
• Première permutation avec la chaine cab
  • Le premier caractère va en bout de chaine : abc
  • le second va en bout de chaine : acb

Nous obtenons bien nos 6 combinaisons : bca, bac, cab, cba, abc, acb.

Le code

Les variables publiques permettant le stockage des différentes combinaisons au fur et à mesure :

'  A déclarer en entête de votre Module
Dim Tb(), IndTab As Long

La procédure d'appel :

Sub Appel_Combinaisons()
' La procédure Combiner a besoin de deux paramètres :
' La chaine : strText
' La sous chaine permettant la permutation : debut
' Celle-ci, lors de l'appel est bien évidemment vide
Combiner "AZE", ""
End Sub

La procédure récursive effectuant les permutations, toujours grâce à la fonction Mid.

Sub Combiner(strText As String, debut As String)
Dim i As Integer

If Len(strText) = 1 Then ' Lorsque la longueur de strText égale 1 
    ' On stocke la chaine composée de : debut et strText
    ReDim Preserve Tb(IndTab)
    Tb(IndTab) = debut & strText
    IndTab = IndTab + 1
Else
    For i = 1 To Len(strText)
        ' On envoie le premier caractère de la sous-chaine strText au bout
        Combiner Mid(strText, 2, Len(strText) - 1), debut & Mid(strText, 1, 1)
        ' Travail sur la chaine de caractères
        strText = Mid(strText, 2, Len(strText) - 1) & Mid(strText, 1, 1)
    Next
End If
End Sub

Nota : Afin d'améliorer la compréhension de ce code, je vous invite à le lancer en mode pas à pas F8 depuis l'éditeur VBA.

Recherche dans une variable tableau

Analyse

Cet exercice est une traduction, en VBA, de l'algorithme de Dichotomie trouvé ICI (voir chapitre : Algorithme de recherche par dichotomie).

Sans vouloir tout réexpliquer, en gros, la procédure doit :

• comparer la valeur cherchée avec celle située au milieu de la variable tableau
  • Si la valeur cherchée est supérieure à celle du milieu => on cherche dans la moitié supérieure du tableau (récursivité)
  • si elle est inférieure à celle du milieu => on cherche dans la moitié inférieure du tableau (récursivité)
  • Si elles sont égales => retourner l'indice (Milieu en l'occurrence)
  • si la borne inférieure > = borne supérieure : la valeur n'existe pas.

Ces deux derniers points constituent les points d'arrêt.

Le code

Le code d'appel de la fonction

Sub Appel()
Dim Tb_In(10) As Integer, Ind As Integer, k As Integer

' remplissage de notre tableau
For k = 1 To 31 Step 3
    Tb_In(Ind) = k
    Ind = Ind + 1
Next k
MsgBox Est_Situe_Dans_Tableau_A_Lindice(Tb_In(), 19, LBound(Tb_In), UBound(Tb_In))End Sub

La fonction récursive

Ces paramètres obligatoires sont :

• La variable tableau contenant toutes les données : procédure d'appel : Tb_In(), Fonction : Tbl()
• La valeur cherchée : procédure d'appel : 19, Fonction : i
• La borne inférieure : procédure d'appel : LBound(Tb_In), Fonction : mini
• La borne supérieure : procédure d'appel : UBound(Tb_In), Fonction : maxi.

Function Est_Situe_Dans_Tableau_A_Lindice(Tbl() As Integer, i As Integer, mini As Integer, maxi As Integer) As Integer
Dim Milieu As Integer
Milieu = (mini + maxi) / 2
If Tbl(Milieu) = i Then ' On a trouvé le nombre i cherché
    Est_Situe_Dans_Tableau_A_Lindice = Milieu
ElseIf mini >= maxi Then ' On n'a pas trouvé i et où on ne peut plus continuer
    Est_Situe_Dans_Tableau_A_Lindice = 0
ElseIf Tbl(Milieu) > i Then 'On peut continuer avec un sous-tableau
    ' le nombre cherché est inférieur à la valeur située au « milieu des 2 bornes du tableau »
    Est_Situe_Dans_Tableau_A_Lindice = Est_Situe_Dans_Tableau_A_Lindice(Tbl(), i, mini, Milieu - 1)
Else
    ' le nombre cherché est supérieur à la valeur située au « milieu des 2 bornes du tableau »
    Est_Situe_Dans_Tableau_A_Lindice = Est_Situe_Dans_Tableau_A_Lindice(Tbl(), i, Milieu + 1, maxi)
End If
End Function

Conclusion

Je précise ne rien avoir inventé ici. Je suis parti d'algorithmes tout simples que l'on peut trouver soi-même ou sur Internet et les ai transcrit en petites fonctions récursives en langage VBA.