Fonction Insère, arguments 11 : nombre,
l : liste
Si la listel est vide , Insère :={11}
Si la li ste l n ' est pas vide , on la
décompose en tête t et queue q
Si 11 < t alors Insère := 11 : : l
sinon Insère := t : : Insère ( 11 , q)
L'a lgorithme est simple,
On peut démontrer que cette fo ncti on
réalise bien une insertion d ' un nombre
n da ns une li ste triée I par récurre nce
sur la longueur de /.
• Si cette longueur est nulle, la li ste est
vide. la premi ère ligne du corps de la
fo nction s'applique , le résultat est donc
COITect.
• Admettons que le résultat so it correct
pour une li ste de longueur p et considérons une liste de longueur p + l . La
li ste se décompose en tête t et queue q .
Sin < t , il est mi s en première position ,
sinon il est inséré dans la queue.
Cette qu e ue es t de lo ng ue ur p donc
In ère (n , q) donne le bon rés ultat. . . on
en déduit que Insère (n, /)auss i. Ainsi,
par réc urrence, la fo nction renvoie bien
toujours le résultat attendu . L' intérêt de
la récursivité est là: la facilité et la clarté
de la programmation, la brièveté du programme ... et surtout la poss ibilité de
pro uver que les fo nction s fo urni ssent
bien les résultats attendus !
À partir de cette fo nction d ' insertion, il
POUR L'INFORMATIQUE
- Si cette longueur est nulle , la liste est
vide, la première ligne du corps de la
fonction s'applique, le résultat est donc
correct.
-Admettons que le résultat soit correct
pour une li ste de longueur p et considérons une li ste de longueur p + 1 . La
li ste se décompose en tête t et queue q.
Cette queue est de longueur p donc Tri (q)
do nne le bo n résultat. Comme Insère
donne éga lement le bon résultat ... on
en déduit que Tri (/) auss i. On conclut
à nouveau par récurrence.
est fac ile de créer une fo nction de tri :
Ces que lques exemples justifient l'affi rmatio n : av ec la réc ursivité, proFonction Tri , argument : l : liste
Si la liste lest vide alors Tri := l
Si la liste l n ' est pas vide, on la
décompose en tête t et queue q alors :
Tri := Insère (t , Tri (q))
De même que pour la fo nction d ' insertion. cette fo nction se prouve par récurrence sur la longueur de la li ste I :
grammer, c'est prouver.
H . L.
Hors-serie n• 52. Mathematiques & informatique Tangente
l : liste
Si la listel est vide , Insère :={11}
Si la li ste l n ' est pas vide , on la
décompose en tête t et queue q
Si 11 < t alors Insère := 11 : : l
sinon Insère := t : : Insère ( 11 , q)
L'a lgorithme est simple,
On peut démontrer que cette fo ncti on
réalise bien une insertion d ' un nombre
n da ns une li ste triée I par récurre nce
sur la longueur de /.
• Si cette longueur est nulle, la li ste est
vide. la premi ère ligne du corps de la
fo nction s'applique , le résultat est donc
COITect.
• Admettons que le résultat so it correct
pour une li ste de longueur p et considérons une liste de longueur p + l . La
li ste se décompose en tête t et queue q .
Sin < t , il est mi s en première position ,
sinon il est inséré dans la queue.
Cette qu e ue es t de lo ng ue ur p donc
In ère (n , q) donne le bon rés ultat. . . on
en déduit que Insère (n, /)auss i. Ainsi,
par réc urrence, la fo nction renvoie bien
toujours le résultat attendu . L' intérêt de
la récursivité est là: la facilité et la clarté
de la programmation, la brièveté du programme ... et surtout la poss ibilité de
pro uver que les fo nction s fo urni ssent
bien les résultats attendus !
À partir de cette fo nction d ' insertion, il
POUR L'INFORMATIQUE
- Si cette longueur est nulle , la liste est
vide, la première ligne du corps de la
fonction s'applique, le résultat est donc
correct.
-Admettons que le résultat soit correct
pour une li ste de longueur p et considérons une li ste de longueur p + 1 . La
li ste se décompose en tête t et queue q.
Cette queue est de longueur p donc Tri (q)
do nne le bo n résultat. Comme Insère
donne éga lement le bon résultat ... on
en déduit que Tri (/) auss i. On conclut
à nouveau par récurrence.
est fac ile de créer une fo nction de tri :
Ces que lques exemples justifient l'affi rmatio n : av ec la réc ursivité, proFonction Tri , argument : l : liste
Si la liste lest vide alors Tri := l
Si la liste l n ' est pas vide, on la
décompose en tête t et queue q alors :
Tri := Insère (t , Tri (q))
De même que pour la fo nction d ' insertion. cette fo nction se prouve par récurrence sur la longueur de la li ste I :
grammer, c'est prouver.
H . L.
Hors-serie n• 52. Mathematiques & informatique Tangente