Langages et récursivité
• Adme tton s qu ' e lle le so it po ur n - 1
(hypoth èse de récurrence) :
v,,_ 1 = (n - l )(n - 4) / 2.
• Al o rs, d 'a près la re lat io n de réc urre nce:
v,, = v,,_ 1 + n - 2
= (n - 1 )(n - 4) / 2 + n - 2
= (n
2 - Sn + 4 + 2n - 4) / 2
= (n
2 - 311 )/2 = n(n -3)/2
La fo rmule est do nc vra ie po ur n.
• De proc he e n proc he (on dit e ncore
par récurrence), o n e n déduit q u 'ell e
est vraie po ur to ut n ~ 3 .
li s 'ag it de ! 'archétype du raisonne me nt
pa r récurre nce. Co mme o n va le vo ir, il
s'applique à l' ide ntique po ur pro uve r
que les fo nctions récursives rempli ssent
bi e n le ur office.
li est do nc à la base de la récursivité.
de la fo nction décrit comment elle est défini e. Cette définiti o n pe ut se mbler étonnante, car la factorielle y est défini e à paitir
d 'ell e-mê me. On la compre nd mieux en
pe nsant à un e délégati o n de tâc he. Vo ulo ir sui vre son exécutio n est fast id ie ux
e t, de plus, ne sert à ri e n (l'encadré c ico ntre s imul e ce pe nda nt l'exéc uti o n
compl è te de la procéd ure). L' intérêt est
de po uvo ir pro uver que la fo ncti o n Facto ri e ll e re mp lit bie n son rô le. Ce la se
fa it par réc urre nce sur son arg ume nt 11.
O n re ma rque que l'écriture de la fo ncti o n est e ll e- mê me la pre uve q u 'e ll e
do nne bi e n le bo n résul tat. En effet, si
n = 0 , le résultat est bi e n 1. Ad me tto ns
que le résultat soit bi e n (n - 1) 1 pour
n - 1, la re lati o n Facto ri e ll e: = 11 x Facto ri e lle (n - 1) do nne 11 (n - 1) ! = 11 !
po ur n , ce qui est le bo n résultat. O n a
Description d'une fonction récursiue
ainsi mo ntré par récurre nce que la fo ncti o n Facto ri e lle re nvo ie do nc to ujours
La démarche précéde nte permet de créer
le bo n résultat.
des algorithmes avant de les prouver.
L' impo rta nt est de res te r a u cœ ur du
le tri par récursiuité
princ ipe: s i o n sa it passer de l'éta pe 11
à l'éta pe n + 1 e t que l'on sa it démarrer , o n pe ut tra ite r to utes les é tapes.
Qua nd o n l' applique e n info rmatique,
o n ne parl e plu s de réc urre nce mais de
récursivité.
On pe ut ainsi définir des fonctions récursives da ns pra tique me nt to us les langages mode rnes.
L'exe mpl e le plu s so uve nt do nné est
celui de la fo nctio n fac to ri elle do nt voici
la desc ripti o n du ca lc ul :
Fonction Factorielle, argument n : nombre
Si n = 0 alors Factorielle := 1
sinon Factorielle := n x Factorielle (11 - 1)
Co mme da ns un grand nombre de langages, on a fait précéde r la descripti o n
de cette fon cti on par une partie déclarant
son no m (Facto rie lle) et son (o u ses)
argument : n qui est un no mbre . Le corps
Les fo nc ti o ns réc urs ives sont parti culiè re me nt intéressantes s i ell es s'appli -
que nt à des structures récursives comme
les li stes o u les arbres . Vo ici la défi ni -
tio n , a priori surréali ste, de la structure
de li ste :
Une liste cl ' obj ets est soit fa liste vide.
soit un obj et (la tête) plus une liste (fa
queue). Une li ste de no mbres e nti e rs
pe ut do nc être: { 10. 5 , 8, 2}. Dans ce
cas, sa tête est le nombre 10 et sa que ue,
la li ste {5, 8, 2}. Po ur ce qui suit , o n
no tera t : : q la I iste de tê te t e t de queue
q. Un exemple de fo ncti o n récursive sur
les li stes va dé bo uche r sur un tri . Comme nt trier une li ste par ordre croissant ?
Comme o n va le vo ir, il suffit de savoir
in sérer un no mbre dans une li ste déjà
triée. La fo nctio n sui va nte, notée Insère ,
sera utili sée po ur ce fa ire :
Tangente Hors-serie n°52. Mathematiques & informatique
• Adme tton s qu ' e lle le so it po ur n - 1
(hypoth èse de récurrence) :
v,,_ 1 = (n - l )(n - 4) / 2.
• Al o rs, d 'a près la re lat io n de réc urre nce:
v,, = v,,_ 1 + n - 2
= (n - 1 )(n - 4) / 2 + n - 2
= (n
2 - Sn + 4 + 2n - 4) / 2
= (n
2 - 311 )/2 = n(n -3)/2
La fo rmule est do nc vra ie po ur n.
• De proc he e n proc he (on dit e ncore
par récurrence), o n e n déduit q u 'ell e
est vraie po ur to ut n ~ 3 .
li s 'ag it de ! 'archétype du raisonne me nt
pa r récurre nce. Co mme o n va le vo ir, il
s'applique à l' ide ntique po ur pro uve r
que les fo nctions récursives rempli ssent
bi e n le ur office.
li est do nc à la base de la récursivité.
de la fo nction décrit comment elle est défini e. Cette définiti o n pe ut se mbler étonnante, car la factorielle y est défini e à paitir
d 'ell e-mê me. On la compre nd mieux en
pe nsant à un e délégati o n de tâc he. Vo ulo ir sui vre son exécutio n est fast id ie ux
e t, de plus, ne sert à ri e n (l'encadré c ico ntre s imul e ce pe nda nt l'exéc uti o n
compl è te de la procéd ure). L' intérêt est
de po uvo ir pro uver que la fo ncti o n Facto ri e ll e re mp lit bie n son rô le. Ce la se
fa it par réc urre nce sur son arg ume nt 11.
O n re ma rque que l'écriture de la fo ncti o n est e ll e- mê me la pre uve q u 'e ll e
do nne bi e n le bo n résul tat. En effet, si
n = 0 , le résultat est bi e n 1. Ad me tto ns
que le résultat soit bi e n (n - 1) 1 pour
n - 1, la re lati o n Facto ri e ll e: = 11 x Facto ri e lle (n - 1) do nne 11 (n - 1) ! = 11 !
po ur n , ce qui est le bo n résultat. O n a
Description d'une fonction récursiue
ainsi mo ntré par récurre nce que la fo ncti o n Facto ri e lle re nvo ie do nc to ujours
La démarche précéde nte permet de créer
le bo n résultat.
des algorithmes avant de les prouver.
L' impo rta nt est de res te r a u cœ ur du
le tri par récursiuité
princ ipe: s i o n sa it passer de l'éta pe 11
à l'éta pe n + 1 e t que l'on sa it démarrer , o n pe ut tra ite r to utes les é tapes.
Qua nd o n l' applique e n info rmatique,
o n ne parl e plu s de réc urre nce mais de
récursivité.
On pe ut ainsi définir des fonctions récursives da ns pra tique me nt to us les langages mode rnes.
L'exe mpl e le plu s so uve nt do nné est
celui de la fo nctio n fac to ri elle do nt voici
la desc ripti o n du ca lc ul :
Fonction Factorielle, argument n : nombre
Si n = 0 alors Factorielle := 1
sinon Factorielle := n x Factorielle (11 - 1)
Co mme da ns un grand nombre de langages, on a fait précéde r la descripti o n
de cette fon cti on par une partie déclarant
son no m (Facto rie lle) et son (o u ses)
argument : n qui est un no mbre . Le corps
Les fo nc ti o ns réc urs ives sont parti culiè re me nt intéressantes s i ell es s'appli -
que nt à des structures récursives comme
les li stes o u les arbres . Vo ici la défi ni -
tio n , a priori surréali ste, de la structure
de li ste :
Une liste cl ' obj ets est soit fa liste vide.
soit un obj et (la tête) plus une liste (fa
queue). Une li ste de no mbres e nti e rs
pe ut do nc être: { 10. 5 , 8, 2}. Dans ce
cas, sa tête est le nombre 10 et sa que ue,
la li ste {5, 8, 2}. Po ur ce qui suit , o n
no tera t : : q la I iste de tê te t e t de queue
q. Un exemple de fo ncti o n récursive sur
les li stes va dé bo uche r sur un tri . Comme nt trier une li ste par ordre croissant ?
Comme o n va le vo ir, il suffit de savoir
in sérer un no mbre dans une li ste déjà
triée. La fo nctio n sui va nte, notée Insère ,
sera utili sée po ur ce fa ire :
Tangente Hors-serie n°52. Mathematiques & informatique