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.
