IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Récursivité en VBA Access

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 : 12 commentaires Donner une note à l´article (5)

Article lu   fois.

L'auteur

Profil Pro

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

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
Sélectionnez
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
Sélectionnez
Fact(n)=Fact(n-1)*n

avec :

premier terme
Sélectionnez
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
Sélectionnez
'*********************************************************************************************************************
'**************************************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
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 AccessLibrairie 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
Sélectionnez
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
Sélectionnez
Fibo(n)=Fibo(n-2)+Fibo(n-1)

ou encore par son équivalent :

formule récursive
Sélectionnez
Fibo(n)=Fibo(n-1)+Fibo(n-2)

avec :

premiers termes
Sélectionnez
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
Sélectionnez
'*********************************************************************************************************************
'***********************************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
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
Sélectionnez
'*********************************************************************************************************************
'*************************************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
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 CRé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
Sélectionnez
'********************************************************************************************************************
'***************************************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
Sélectionnez
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
Sélectionnez
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
Sélectionnez
'*********************************************************************************************************************
'******************************************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
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
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)
Sélectionnez
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
Sélectionnez
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)
Sélectionnez
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
Sélectionnez
(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
Cacher/Afficher le codeSélectionnez
Fonction appelante EvaluerExpression
Sélectionnez
'*********************************************************************************************************************
'***************************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
appels successifs - expression arithmétique

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

La base jointeBD Récursivité 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 stockArborescence dans un logiciel de gestion de stock proposé par f-leb et traitant de la récursivité dans Access.

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

Arrangements et combinaisons dans AccessArrangements 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.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

Copyright © 2017 Denis Hulo. Aucune reproduction, même partielle, ne peut être faite de ce site ni 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. Droits de diffusion permanents accordés à Developpez LLC.