A
B
1
I
p
Un polygone convexe à n sommets
est obtenu d ' un polygone convexe P
à n - 1 sommets en ajoutant un point A
entre deux sommets B et C (côtés en
rouge) . Les diagonales sont alors
de trois types : celles de P, BC et celles
passant par A (en bleu).
Voyo ns un exemple où ce principe est
à l'œuvre: combien de diagonales un polygo ne convexe à n côtés possède-t-il ?
Tout d'abord, nous lui donnons un nom :
v
11
• Nom mer est pre ndre un pouvoir sur
ce que l' o n no mme. Le raisonne ment
s' opère en li ant le cas d' un po lygone à
n côtés à celui d ' un polygone à n - 1
côtés. On considère donc un po lygone
P à n - 1 côtés et on y ajo ute un po int
A entre deux sommets B et C.
Le s diago na les se sc in de nt e n tro is
groupes. Le pre mier est formé des d iagonales du po lygone P, au nombre de
v
11
_ 1
par hypothèse, le seco nd d u côté
BC de Pet le troisième des dro ites joigna nt A aux points de P autres que B et
C, au nombre den - 3.
Ai nsi : v 11 = v,,_ 1 + 1 + (n - 3)
Une telle re lation est dite de récurrence
car elle lie v
11
à v
11
_ 1
• Si on connaît v
11
_ 1
,
on en déd uit v
11
• La conn aissance d' un
terme permet de calculer, les sui vants.
Comme un triangle n'a aucune diagonale,
v 3 = 0 ce qui donne les suivants de proche.
On peut même en déduire une formu le
POUR L'INFORMATIQUE
La récursivité en mémoire
La procédure ci-dessous décrit en détail comment la fonction Factorielle fonctionne pour n = 3 :
• Comme 3 n'est pas égal à o, l'appel de Factorielle (3) provoque l'affectation de 3 x Factorielle (2), qui demande le
calcul de Factorielle (2), et on recommence.
• Comme 2 n'est pas égal à o, l'appel de Factorielle (2) provoque l'affectation de 2 x Factorielle (1), qui demande le
calcul de Factorielle (1), et on recommence.
• Comme 1 n'est pas égal à o, l'appel de Factorielle (1) provoque l'affectation de 1 x Factorielle (o), qui demande le
calcul de Factorielle (o), et on recommence.
• Comme o est égal à o, l'appel de Factorielle (o) provoque
l'affectation de 1. Les calculs envisagés et laissés de côté
peuvent alors être effectués. On obtient successivement :
Factorielle (1) = 1 x Factorielle (o) = 1 x 1 = 1,
Factorielle (2) = 2 x Factorielle (1) = 2 x 1 = 2,
Factorielle (3) = 3 x Factorielle (2) = 3 x 2 = 6.
Chaque procédure récursive peut se détailler ainsi. Elle
occupe une place en mémoire importante car tous les appels
récursifs doivent être stockés dans un sens, avant d'être exécutés dans l'autre. On comprend que cette description est
inutile dans la pratique, car l'un des intérêts primordiaux
des fonctions récursives est d'être facile à prouver par
récurrence.
donnant v 11
• On trouve: v
11
= n(n - 3)/2.
Comme nt la tro uver ? Le déta il ne sera
pas donné ici, mais il fa ut savo ir q ue
les méthodes sont diverses. L' une d'entre
e lles, q ui n'est pas la plu s nég li geable,
est l' induction .
On é met une hypothèse par intu ition ,
on la vérifie expérimenta le ment pour
les premières valeurs, et, si aucun contreexe m ple ne vient la dé me nti r, o n la
démontre .
La démons tration par récurrence (ce
n'est pas par hasard qu 'elle est appelée
induction par les Anglo-Saxons) est la
preuve de cette form ule a posteriori. Sa
démarche:
• Elle est vérifiée pour n = 3 .
Hors-serie n • 52. Mathematiques & informatique Tangente
B
1
I
p
Un polygone convexe à n sommets
est obtenu d ' un polygone convexe P
à n - 1 sommets en ajoutant un point A
entre deux sommets B et C (côtés en
rouge) . Les diagonales sont alors
de trois types : celles de P, BC et celles
passant par A (en bleu).
Voyo ns un exemple où ce principe est
à l'œuvre: combien de diagonales un polygo ne convexe à n côtés possède-t-il ?
Tout d'abord, nous lui donnons un nom :
v
11
• Nom mer est pre ndre un pouvoir sur
ce que l' o n no mme. Le raisonne ment
s' opère en li ant le cas d' un po lygone à
n côtés à celui d ' un polygone à n - 1
côtés. On considère donc un po lygone
P à n - 1 côtés et on y ajo ute un po int
A entre deux sommets B et C.
Le s diago na les se sc in de nt e n tro is
groupes. Le pre mier est formé des d iagonales du po lygone P, au nombre de
v
11
_ 1
par hypothèse, le seco nd d u côté
BC de Pet le troisième des dro ites joigna nt A aux points de P autres que B et
C, au nombre den - 3.
Ai nsi : v 11 = v,,_ 1 + 1 + (n - 3)
Une telle re lation est dite de récurrence
car elle lie v
11
à v
11
_ 1
• Si on connaît v
11
_ 1
,
on en déd uit v
11
• La conn aissance d' un
terme permet de calculer, les sui vants.
Comme un triangle n'a aucune diagonale,
v 3 = 0 ce qui donne les suivants de proche.
On peut même en déduire une formu le
POUR L'INFORMATIQUE
La récursivité en mémoire
La procédure ci-dessous décrit en détail comment la fonction Factorielle fonctionne pour n = 3 :
• Comme 3 n'est pas égal à o, l'appel de Factorielle (3) provoque l'affectation de 3 x Factorielle (2), qui demande le
calcul de Factorielle (2), et on recommence.
• Comme 2 n'est pas égal à o, l'appel de Factorielle (2) provoque l'affectation de 2 x Factorielle (1), qui demande le
calcul de Factorielle (1), et on recommence.
• Comme 1 n'est pas égal à o, l'appel de Factorielle (1) provoque l'affectation de 1 x Factorielle (o), qui demande le
calcul de Factorielle (o), et on recommence.
• Comme o est égal à o, l'appel de Factorielle (o) provoque
l'affectation de 1. Les calculs envisagés et laissés de côté
peuvent alors être effectués. On obtient successivement :
Factorielle (1) = 1 x Factorielle (o) = 1 x 1 = 1,
Factorielle (2) = 2 x Factorielle (1) = 2 x 1 = 2,
Factorielle (3) = 3 x Factorielle (2) = 3 x 2 = 6.
Chaque procédure récursive peut se détailler ainsi. Elle
occupe une place en mémoire importante car tous les appels
récursifs doivent être stockés dans un sens, avant d'être exécutés dans l'autre. On comprend que cette description est
inutile dans la pratique, car l'un des intérêts primordiaux
des fonctions récursives est d'être facile à prouver par
récurrence.
donnant v 11
• On trouve: v
11
= n(n - 3)/2.
Comme nt la tro uver ? Le déta il ne sera
pas donné ici, mais il fa ut savo ir q ue
les méthodes sont diverses. L' une d'entre
e lles, q ui n'est pas la plu s nég li geable,
est l' induction .
On é met une hypothèse par intu ition ,
on la vérifie expérimenta le ment pour
les premières valeurs, et, si aucun contreexe m ple ne vient la dé me nti r, o n la
démontre .
La démons tration par récurrence (ce
n'est pas par hasard qu 'elle est appelée
induction par les Anglo-Saxons) est la
preuve de cette form ule a posteriori. Sa
démarche:
• Elle est vérifiée pour n = 3 .
Hors-serie n • 52. Mathematiques & informatique Tangente