SAVOIRS
par Herve Lehning
Langages et
récursiuité
La notion d'autoréférence fascine les amateurs de paradoxes
et de jeux mathématiques. En informatique, c'est la récursivité
qui joue ce rôle. Elle consiste à appeler au sein d'un
programme qui calcule la fonctionf. .. la fonctionf elle-même !
Il n 'y a pourtant rien de plus sûr qu'une telle démarche.
L
es premi ers langages de programm ati o n co mm e C OBOL
pour la gesti on ou FORTR A
pour le calcul sc ientifique se passa ient
de réc ursi vité, il s ava ient bien tort ' Si
auj ourd ' hui , sa ns doute, tous les langages so nt réc ursifs, l ' une des rai sons
es t prob abl ement l a sûreté, les programmes récursifs étant pratiquement les
seul s dont on puisse démontrer qu ' ils font
bien ce qu ' il s sont censés fa ire ... Dans
les di cti onn aires, la définiti on la plu s
courante du mot récursif est siby lline:
Un programm e info rmatiqu e es t dit
récursif s'il demande sa propre exécution au cours de son déroulement. Sans
aucun exempl e, ce tte ph rase est bi en
difficile à comprendre ...
Récurrence et induction
Pour comprendre cela, i l est nécessa ire
d 'exp l iquer effecti vement ce qu 'est la
récursivité .. . et pour cela la réc urrence ,
la not ion mathématiqu e dont ell e est
issue.
Tangente Hors-serie n 5..::. athématiques & informatique