Récursivité en VBA Access

Denis Hulo

Objectif : apprendre à créer des fonctions ou des procédures récursives à l'aide d'exemples simples et de schémas pour mieux comprendre le concept.

Niveau requis : avancé.

Commentez cet article : Commentez

- Titre : Récursivité en VBA Access

- Auteur : Denis Hulo

- Parution : 27 juillet 2017

- Public visé :

- Licence : Copyright ® 2017 Denis Hulo. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Introduction

- II. Exemples de fonctions récursives

- II-A. Fonction factorielle

- II-A-1. Code VBA

- II-A-2. Structure des appels et remontée des résultats

- II-B. Fonction de Fibonacci

- II-B-1. Code VBA

- II-B-2. Structure des appels et remontée des résultats

- II-C. Limites de la récursivité

- II-C-1. Empilement et remontée

- II-C-2. Débordement de pile (stack overflow)

- II-D. Fonctions récursives terminales

- III. Récursivité et opérations arithmétiques

- III-A. Table nécessaire

- III-A-1. T_Operation

- III-B. Requêtes

- III-B-1. R_Operations (1)

- III-B-2. R_Operations (2)

- III-C. Affichage des données

- III-D. Fonction VBA

- III-E. Structure des appels et remontée des résultats

- IV. La base de données à télécharger

- V. Liens utiles

- VI. Remerciements

I - Introduction

Récursivité : en informatique et en logique, une fonction ou plus généralement un algorithme qui contient un appel à lui-même est dit récursif.

Nombreux sont les exemples dans lesquels on utilise la récursivité :

- fonctions mathématiques récursives, comme la factorielle ;

- représentation et évaluation d'expressions arithmétiques composées de plusieurs opérations ;

- génération des arrangements ou des combinaisons de p éléments pris dans n ;

- création d'un arbre généalogique à partir d'informations stockées dans une base de données.

Nous présenterons pour commencer deux exemples simples de fonctions mathématiques récursives écrites en VBA, accompagnées de schémas affichant les structures d'appels récursifs. Enfin, dans la 3e partie, nous étudierons le cas de la génération et de l'évaluation d'expressions arithmétiques à partir de données enregistrées dans une base Access.

II - Exemples de fonctions récursives

Commençons par décrire des exemples simples de fonctions mathématiques récursives.

II-A - Fonction factorielle

En mathématiques, la factorielle d'un entier naturel n est le produit des nombres entiers strictement positifs inférieurs ou égaux à n.

Si on considère la fonction Fact(n) donnant la factorielle de n, les premières valeurs de cette fonction sont :

exemples de résultats

Fact(0) = 1
Fact(1) = 1
Fact(2) = (1)*2 = 2
Fact(3) = (1*2)*3 = 6
Fact(4) = ((1*2)*3)*4 = 24
...

On voit que la récursivité de la fonction factorielle peut être définie par l'expression :

formule récursive

Fact(n)=Fact(n-1)*n

avec :

premier terme

Fact(0)=1

Pour n=0, la fonction vaut 1. Comme on le verra plus loin, cette condition permet l'arrêt des appels récursifs de la fonction VBA et la remontée des résultats.

II-A-1 - Code VBA

Sa traduction en VBA est assez simple :

Fonction factorielle

'*********************************************************************************************************************
'**************************************Fonction récursive de la factorielle*******************************************
'*********************************************************************************************************************
Function Fact(n As Long) As Long
' n: argument de la factorielle

If n = 0 Then ' condition de sortie et d'arrêt des appels récursifs
Fact = 1
Else
' appel de la fonction pour (n-1)
Fact = Fact(n - 1) * n ' remontée du résultat pour Fact(n-1) et calcul de Fact(n)
End If

End Function

Pour ne pas compliquer les choses, on ne traite pas le cas où la valeur entrée est inférieure à 0 (n<0).

II-A-2 - Structure des appels et remontée des résultats

La fonction génère des appels récursifs successifs pour Fact(n), Fact(n-1),..,Fact(0), puis remonte les résultats à partir de Fact(0)=1 (condition de sortie), puis Fact(1)=Fact(0)*1=1*1,.., Fact(n)=Fact(n-1)*n, suivant le schéma :

appels successifs - factorielle de 6

Pour afficher les différentes structures d'appels des fonctions, on utilise le contrôle CtrlTree inséré dans un formulaire. Il nécessite l'installation d'une bibliothèque. Pour plus de détails, vous pouvez consulter la page Librairie pour arbres, grilles et listes sous Access.

II-B - Fonction de Fibonacci

La suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Elle commence généralement par les termes 0 et 1 (parfois 1 et 1) et ses premiers termes sont : 0, 1, 1, 2, 3, 5, 8, 13, 21, etc.

Si on considère la fonction Fibo(n) donnant les termes de cette suite d'indice n, les premières valeurs de cette fonction sont :

exemples de termes

Fibo(0) = 0
Fibo(1) = 1
Fibo(2) = 1 + 1 = 2
Fibo(3) = 1 + 2 = 3
Fibo(4) = 2 + 3 = 5
...

Sa récurrence peut ainsi être définie par l'expression :

formule récursive

Fibo(n)=Fibo(n-2)+Fibo(n-1)

ou encore par son équivalent :

formule récursive

Fibo(n)=Fibo(n-1)+Fibo(n-2)

avec :

premiers termes

Fibo(0)=0
Fibo(1)=1

Pour n=0 et n=1, la fonction vaut respectivement 0 et 1. Comme on le verra plus loin pour la fonction VBA, ces conditions permettent l'arrêt des appels récursifs et la remontée des résultats.

II-B-1 - Code VBA

Sa traduction en VBA ne pose pas de problème particulier :

fonction Fibonacci

'*********************************************************************************************************************
'***********************************Fonction récursive de la suite de Fibonacci***************************************
'*********************************************************************************************************************
Function Fibo(n As Long) As Long
' n: nombre de termes de la suite de Fibonacci

If (n = 0) Then ' condition de sortie et d'arrêt des appels récursifs
Fibo = 0
ElseIf (n = 1) Then ' condition de sortie et d'arrêt des appels récursifs
Fibo = 1
Else
' appel de la fonction Fibo pour (n-2) et (n-1)
Fibo = Fibo(n - 2) + Fibo(n - 1) ' remontée du résultat pour Fibo(n-2) et Fibo(n-1), puis calcul de Fibo(n)
End If

End Function

Pour ne pas compliquer les choses, on ne traite pas le cas où la valeur entrée est inférieure à 0 (n<0).

II-B-2 - Structure des appels et remontée des résultats

La fonction génère des appels récursifs successifs pour Fibo(n), Fibo(n-1),..,Fibo(0), puis remonte les résultats à partir de Fibo(0)=0 et Fibo(1)=1 (conditions de sortie), puis Fibo(2)=Fibo(0)+Fibo(1) = 1 + 1,.., Fibo(n)=Fibo(n-2)+Fibo(n-1), suivant le schéma :

appels successifs - fibonacci de 4

II-C - Limites de la récursivité

Même si les fonctions récursives peuvent être un moyen commode et élégant pour résoudre des problèmes variés, elles ont aussi leur limite au niveau du stockage des données en mémoire, et peuvent ainsi provoquer assez rapidement des débordements de pile (stack Overflow).

Illustrons ce cas de figure avec la fonction Sigma(n) qui calcule la somme des n premiers entiers en partant de 1 :

fonction Sigma

'*********************************************************************************************************************
'*************************************Fonction Sigma - somme des n premiers entiers***********************************
'*********************************************************************************************************************
Function Sigma(ByVal n As Long) As Long
' n: nombre d'entiers sommés

If n = 1 Then ' condition de sortie et d'arrêt des appels récursifs
Sigma = 1 ' renvoie 1
Else
' appel de la fonction pour (n-1)
Sigma = Sigma(n - 1) + n ' remontée du résultat pour Sigma(n-1) et calcul de Sigma(n)
End If

End Function

Pour éviter l'erreur de dépassement de capacité rencontrée pour de grandes valeurs, il vaut mieux préférer le type Long (entier long) au type Integer (entier court).

II-C-1 - Empilement et remontée

La phase de descente et de remontée dans la pile des appels de la fonction récursive pour Sigma(6) :

descente et remontée dans la pile

Au cours de la phase de descente, les valeurs des arguments de n=6 à n=1 sont donc stockées successivement dans la pile et ce n'est qu'au moment de la remontée, donc également au moment où la condition de sortie est vraie, que les appels enregistrés sont dépilés au fur et à mesure de la remontée. Ici pour des petits calculs cela convient très bien, mais lorsqu'il s'agit de faire de plus profondes récursions cela peut provoquer un dépassement de capacité avec un espace de pile insuffisant.

Pour plus de détails, je vous invite à consulter la page Récursivité en langage C.

II-C-2 - Débordement de pile (stack overflow)

La pile est un emplacement mémoire destiné à mémoriser les paramètres, les valeurs des variables locales, mais aussi les adresses des fonctions en cours d'exécution. Le volume de données est donc important et un débordement de la pile peut très vite arriver.

Pour le vérifier, déterminons à partir de quel entier Sigma génère un débordement de pile.

Pour cela, on va écrire une fonction principale comportant une gestion d'erreur, qui va appeler dans une boucle la fonction Sigma successivement pour 1, 2, 3… jusqu'à provoquer l'erreur de dépassement de pile pour un entier n<10000, erreur que l'on récupérera dans la routine principale pour afficher la valeur de n.

TesterSigma

'********************************************************************************************************************
'***************************************Fonction test du débordement de pile*****************************************
'********************************************************************************************************************
Public Function TesterSigma() As Long
On Error GoTo err_TesterSigma ' gestion d'erreur
Dim i As Long

For i = 1 To 100000
Call Sigma(i) ' appel de la fonction pour i

Next i

Exit Function
err_TesterSigma:

Debug.Print Err.Description + " pour Sigma(" + i + ")" ' affichage de l 'erreur

End Function

Avec ma machine, j'obtiens un débordement de pile pour n proche de 6284, cette valeur pouvant varier en fonction de la mémoire de la pile d'appels. En VBA, la mémoire de la pile d'appels étant très petite, on est très vite bloqué.

II-D - Fonctions récursives terminales

On peut aussi réécrire les fonctions récursives pour éviter la remontée des résultats et donc leur empilement.

fonction récursive simple

Function récursionNonTerminale(n)
...
récursionNonTerminale = n + récursionNonTerminale(n - 1)
End Function

Dans ce cas, on remarque que l'instruction est une expression faisant intervenir l'appel récursif, tous les résultats intermédiaires doivent donc être conservés en mémoire.

fonction récursive terminale

Function récursionTerminale(n)
...
récursionTerminale = récursionTerminale(n - 1)
End Function

Ici, aucune référence aux résultats précédents n'est à conserver en mémoire.

Si on reprend l'exemple de la somme des n premiers entiers, suivant ce principe la fonction récursive terminale Sigma2 nécessite alors un 2e argument s, nommé accumulateur, pour calculer la somme :

Sigma2

'*********************************************************************************************************************
'******************************************Fonction récursive terminale Sigma2****************************************
'*********************************************************************************************************************
Function Sigma2(ByVal n As Long, ByVal s As Long) As Long
' n: nombre d'entiers sommés
If n = 1 Then ' condition de sortie et d'arrêt des appels récursifs
Sigma2 = s ' renvoie la somme s terminale, sans remontée de résultat
Else
' appel de la fonction pour (n-1)
Sigma2 = Sigma2(n - 1, s + (n - 1))  ' calcul de la somme dans le 2e argument
End If
End Function

Schéma des appels récursifs de la fonction pour Sigma2(6,6) :

appels récursifs de Sigma2

Le schéma montre qu'il n'y a qu'une phase de descente, mais pas de remontée. De cette manière nous économisons l'utilisation de la pile du programme, et nous gagnons également du temps en exécution.

III - Récursivité et opérations arithmétiques

Une expression arithmétique peut être représentée par une structure arborescente :

arbre représentant une expression arithmétique

Pour créer une expression arithmétique, on a besoin d'enregistrer dans une table T_Operation, les différentes opérations et leurs liens.

III-A - Table nécessaire

III-A-1 - T_Operation

T_Operation

Nom du champ

Type du champ

Description

NumOperation

Entier long

Numéro de l'opération

Valeur1

Numérique

Opérande n°1 à gauche de l'opérateur

Operateur

Texte

Opérateur arithmétique : +, -, *, /

Valeur2

Numérique

Opérande n°2 à droite de l'opérateur

IDOperationDescendante1

Entier long

Clé étrangère qui identifie la sous-opération correspondant au terme de gauche

IDOperationDescendante2

Entier long

Clé étrangère qui identifie la sous-opération correspondant au terme de droite

III-B - Requêtes

III-B-1 - R_Operations (1)

Requête servant de base pour le calcul des résultats intermédiaires :

R_Operations (1)

SELECT NumOperation, Valeur1, Operateur, Valeur2, Switch([Operateur]="+",[Valeur1]+[Valeur2],[Operateur]="-",[Valeur1]-[Valeur2],[Operateur]="*",[Valeur1]*[Valeur2],[Operateur]="/",[Valeur1]/[Valeur2]) AS Resultat, IdOperationDescendante1, IdOperationDescendante2
FROM T_Operation
ORDER BY NumOperation;

Dans laquelle le champ calculé :

champ Resultat

Resultat : Switch([Operateur]="+",[Valeur1]+[Valeur2],[Operateur]="-",[Valeur1]-[Valeur2],[Operateur]="*",[Valeur1]*[Valeur2],[Operateur]="/",[Valeur1]/[Valeur2])

Permet de calculer le résultat de chaque opération arithmétique.

III-B-2 - R_Operations (2)

Requête servant de base à la fonction VBA pour le calcul de l'expression arithmétique :

R_Operations (2)

SELECT NumOperation, Valeur1, Operateur, Valeur2, Switch([Operateur]="+",[Valeur1]+[Valeur2],[Operateur]="-",[Valeur1]-[Valeur2],[Operateur]="*",[Valeur1]*[Valeur2],[Operateur]="/",[Valeur1]/[Valeur2]) AS Resultat, IdOperationDescendante1, IdOperationDescendante2, (Select Max(NumOperation) as m from T_Operation As T1  where (Not IsNull(IdOperationDescendante1)) or( Not IsNull(IdOperationDescendante2)))=[NumOperation] AS Racine
FROM T_Operation
ORDER BY NumOperation;

Dans laquelle la sous-requête :

sous-requête

(Select Max(NumOperation) as m from T_Operation As T1  where (Not IsNull(IdOperationDescendante1)) or( Not IsNull(IdOperationDescendante2)))

Permet de savoir si l'opération est à la racine dans la structure arborescente de l'expression arithmétique.

III-C - Affichage des données

Liste des opérations composant l'expression arithmétique

R_Operation (1)

NumOperation

Valeur1

Operateur

Valeur2

Resultat

IDOperationDescendante1

IDOperationDescendante2

1

10

+

20

30

2

2

*

5

10

3

30

*

10

300

1

2

4

300

+

50

350

3

5

350

*

10

3500

4

6

3500

/

100

35

5

Les valeurs en rouge sont calculées. Le formulaire F_Operations présent dans la base jointe permet une saisie simplifiée des différentes opérations.

III-D - Fonction VBA

La fonction EvalExpression explore de façon récursive, les différentes opérations contenues dans la requête en partant de la racine :

Fonction récursive EvalExpression pour évaluer l'expression

'*********************************************************************************************************************
'***************Fonction récursive pour évaluer l'expression arithmétique définie à partir des données****************
'*********************************************************************************************************************
Public Function EvalExpression(rs As DAO.Recordset, bk As Variant) As Single
' rs : recordset relié à la requête R_Operations pour afficher les opérations et leurs liens
' bk : bookmark ou signet indiquant la position de l'enregistrement correspondant à l'opération courante
Dim Operateur As String ' Opérateur
Dim OperandeGauche As Single, OperandeDroit As Single ' valeurs entrant dans l'opération
Dim NumOperation As Long ' numéro de l'opération
Dim IdOperationDescendante1 As Long, IdOperationDescendante2 As Long ' identifiants des opérations descendantes
Dim bk1 As Variant, bk2 As Variant ' les signets permettant de se positionner sur le bon enregistrement, pour descendre à gauche ou à droite dans l'arbre des opérations
NumOperation = rs!NumOperation ' enregistrement du numéro de l'opération pour savoir si elle a des descendants

rs.Bookmark = bk ' positionnement sur l'opération courante

IdOperationDescendante1 = Nz(rs!IdOperationDescendante1, 0)
IdOperationDescendante2 = Nz(rs!IdOperationDescendante2, 0)

Operateur = rs!Operateur ' opérateur
OperandeGauche = rs!OperandeGauche ' valeur à gauche de l'opération
OperandeDroit = rs!OperandeDroit ' valeur à droite de l'opération

If (IdOperationDescendante1 <> 0) Then ' s'il y a une sous-opération dans la partie gauche de l'opération principale

rs.FindFirst "(NumOperation=" + CStr(IdOperationDescendante1) + ")"  ' recherche de la sous-opération à gauche de cette opération
bk1 = rs.Bookmark ' on enregistre la position de cette sous-opération dans le jeu d'enregistrement

If (IdOperationDescendante2 <> 0) Then ' si une sous-opération à droite

rs.FindFirst "(NumOperation=" + CStr(IdOperationDescendante2) + ")" ' recherche de la sous-opération à droite de cette opération
bk2 = rs.Bookmark ' on enregistre la position de cette sous-opération dans le jeu d'enregistrement

Select Case Operateur ' Choix de l'opérateur

Case "+"
EvalExpression = (EvalExpression(rs, bk1) + EvalExpression(rs, bk2)) ' appel récursif des fonctions pour explorer à gauche et à droite du +

Case "-"
EvalExpression = (EvalExpression(rs, bk1) - EvalExpression(rs, bk2)) ' appel récursif des fonctions pour explorer à gauche et à droite du -

Case "*"
EvalExpression = (EvalExpression(rs, bk1) * EvalExpression(rs, bk2)) ' appel récursif des fonctions pour explorer à gauche et à droite du *

Case "/"
EvalExpression = (EvalExpression(rs, bk1) / EvalExpression(rs, bk2)) ' appel récursif des fonctions pour explorer à gauche et à droite du /

End Select

Else

Select Case Operateur ' Choix de l'opérateur

Case "+"
EvalExpression = (EvalExpression(rs, bk1) + OperandeDroit)    ' appel récursif de la fonction pour explorer à gauche du +

Case "-"
EvalExpression = (EvalExpression(rs, bk1) - OperandeDroit)    ' appel récursif de la fonction pour explorer à gauche du -

Case "*"
EvalExpression = (EvalExpression(rs, bk1) * OperandeDroit)    ' appel récursif de la fonction pour explorer à gauche du *

Case "/"
EvalExpression = (EvalExpression(rs, bk1) / OperandeDroit)    ' appel récursif de la fonction pour explorer à gauche du /

End Select

End If
Else

If (IdOperationDescendante2 <> 0) Then ' s'il y a une sous-opération sur la partie droite de l'opération principale

rs.FindFirst "(NumOperation=" + CStr(IdOperationDescendante2) + ")" ' recherche de la sous-opération à droite de cette opération
bk2 = rs.Bookmark ' on enregistre la position de cette sous-opération dans le jeu d'enregistrement

Select Case Operateur ' Choix de l'opérateur

Case "+"
EvalExpression = (OperandeGauche + EvalExpression(rs, bk2))  ' appel récursif des fonctions pour explorer à droite du +

Case "-"
EvalExpression = (OperandeGauche - EvalExpression(rs, bk2))  ' appel récursif des fonctions pour explorer à droite du -

Case "*"
EvalExpression = (OperandeGauche * EvalExpression(rs, bk2))  ' appel récursif des fonctions pour explorer à droite du *

Case "/"
EvalExpression = (OperandeGauche / EvalExpression(rs, bk2))  ' appel récursif des fonctions pour explorer à droite du /

End Select

Else

Select Case Operateur ' Choix de l'opérateur

Case "+"
EvalExpression = (OperandeGauche + OperandeDroit) ' calcul du résultat entre les 2 valeurs situées sur 2 feuilles

Case "-"
EvalExpression = (OperandeGauche - OperandeDroit) ' calcul du résultat entre les 2 valeurs situées sur 2 feuilles

Case "*"
EvalExpression = (OperandeGauche * OperandeDroit) ' calcul du résultat entre les 2 valeurs situées sur 2 feuilles

Case "/"
EvalExpression = (OperandeGauche / OperandeDroit) ' calcul du résultat entre les 2 valeurs situées sur 2 feuilles

End Select

End If

End If

End Function

Fonction appelante EvaluerExpression

'*********************************************************************************************************************
'***************************Fonction appelante pour évaluer l'expression arithmétique ********************************
'*********************************************************************************************************************
Public Function EvaluerExpression()
Dim db As DAO.Database
Dim rs As DAO.Recordset

Set db = CurrentDb
Set rs = db.OpenRecordset("R_Operations (2)", dbOpenDynaset) ' ouverture de la requête dans le recordset

rs.FindFirst ("Racine=true") ' Position à la racine, opération sans ascendant

EvaluerExpression = EvalExpression(rs, rs.Bookmark) ' appel de la fonction récursive

' Libération des variables
rs.Close
Set rs = Nothing

End Function

III-E - Structure des appels et remontée des résultats

La fonction génère des appels récursifs successifs pour l'expression (((((10+20)*(2*5))+50)*10)/100), suivant le schéma :

appels successifs - expression arithmétique

IV - La base de données à télécharger

La base jointe présente les exemples décrits dans le tutoriel, accompagnés de formulaires affichant les différentes structures d'appels. Elle est au format Access 2000.

V - Liens utiles

Arborescence dans un logiciel de gestion de stock proposé par f-leb et traitant de la récursivité dans Access.

Classification des données dans Access présentant deux exemples sur le même sujet.

Arrangements et combinaisons dans Access décrivant des fonctions récursives permettant de générer des arrangements et des combinaisons.

VI - Remerciements

Je tiens à remercier Arkham46, lolo78 et dourouc05 pour m'avoir conseillé pour la réalisation de cet article, ainsi que Claude Leloup pour sa relecture.