17.11 Règles de récurrence et récursivité
351
© Dunod – La photocopie non autorisée est un délit.
La plupart de ces fonctions peuvent être définies par une formule de récurrence. Par
exemple, la fonction ou T (G T ) est définie comme étant égale à résultatt n dans le
fragment de modèle suivant, qui ne fait appel qu’à l’opérateur binaire ou :
résultatt 1 = Gt 1
résultatt i = résultatt i–1 ou Gt i (i = 2..n)
Cette remarque prendra toute son importance lors de la traduction d’un modèle
abstrait dans une feuille de calcul lorsque le tableur n’offre pas en standard la fonction agrégative utilisée.
17.11 RÈGLES DE RÉCURRENCE ET RÉCURSIVITÉ
Il existe une forme particulière d’expression appelée règle de récurrence. Une telle
règle concerne une grandeur indicée, c’est-à-dire fonction d’une autre grandeur
jouant le rôle de dimension. Cette grandeur indicée se retrouve à la fois en partie
gauche et en partie droite de cette règle. Une règle de récurrence exprime que la
valeur de la grandeur est fonction de sa valeur (ou ses valeurs) précédente(s), ou
même suivante(s), selon la dimension considérée. Prenons l’exemple de la
figure 17.11. On y décrit le suivi d’un poste budgétaire, qui dispose d’une somme
initiale (BUDGET) et fait l’objet de dépenses mensuelles (DEPENSE ti ). On désire
observer l’évolution du montant disponible au début de chaque mois pour ce poste
(BUDGET-DISP ti ).
Figure 17.11 - Règles de récurrence - Contrôle d’un poste budgétaire
On détermine que le montant disponible au début d’un mois est le montant disponible au début du mois précédent duquel on retire le montant des dépenses du mois
précédent. Cette règle n’est pas déterminée pour le premier mois. Il faut donc dans
ce cas donner une formule spéciale, qui détermine la valeur initiale de la suite des
valeurs. On ajoute la grandeur SOLDE qui représente le solde à la fin du dernier
mois.
Données
T = t 1 ..t n
BUDGET
DEPENSE T
Résultats
BUDGET-DISP T
SOLDE
Règles
BUDGET-DISPt 1 = BUDGET
BUDGET-DISPt i = BUDGET-DISPt i–1 - DEPENSEt i–1 (i = 2..n)
SOLDE = BUDGET-DISPt n - DEPENSEt n
351
© Dunod – La photocopie non autorisée est un délit.
La plupart de ces fonctions peuvent être définies par une formule de récurrence. Par
exemple, la fonction ou T (G T ) est définie comme étant égale à résultatt n dans le
fragment de modèle suivant, qui ne fait appel qu’à l’opérateur binaire ou :
résultatt 1 = Gt 1
résultatt i = résultatt i–1 ou Gt i (i = 2..n)
Cette remarque prendra toute son importance lors de la traduction d’un modèle
abstrait dans une feuille de calcul lorsque le tableur n’offre pas en standard la fonction agrégative utilisée.
17.11 RÈGLES DE RÉCURRENCE ET RÉCURSIVITÉ
Il existe une forme particulière d’expression appelée règle de récurrence. Une telle
règle concerne une grandeur indicée, c’est-à-dire fonction d’une autre grandeur
jouant le rôle de dimension. Cette grandeur indicée se retrouve à la fois en partie
gauche et en partie droite de cette règle. Une règle de récurrence exprime que la
valeur de la grandeur est fonction de sa valeur (ou ses valeurs) précédente(s), ou
même suivante(s), selon la dimension considérée. Prenons l’exemple de la
figure 17.11. On y décrit le suivi d’un poste budgétaire, qui dispose d’une somme
initiale (BUDGET) et fait l’objet de dépenses mensuelles (DEPENSE ti ). On désire
observer l’évolution du montant disponible au début de chaque mois pour ce poste
(BUDGET-DISP ti ).
Figure 17.11 - Règles de récurrence - Contrôle d’un poste budgétaire
On détermine que le montant disponible au début d’un mois est le montant disponible au début du mois précédent duquel on retire le montant des dépenses du mois
précédent. Cette règle n’est pas déterminée pour le premier mois. Il faut donc dans
ce cas donner une formule spéciale, qui détermine la valeur initiale de la suite des
valeurs. On ajoute la grandeur SOLDE qui représente le solde à la fin du dernier
mois.
Données
T = t 1 ..t n
BUDGET
DEPENSE T
Résultats
BUDGET-DISP T
SOLDE
Règles
BUDGET-DISPt 1 = BUDGET
BUDGET-DISPt i = BUDGET-DISPt i–1 - DEPENSEt i–1 (i = 2..n)
SOLDE = BUDGET-DISPt n - DEPENSEt n