1. Principe
Un sous-programme peut appeler un autre sous-programme,
quel qu’il soit. Donc un sous-programme peut s’appeler
lui-même. Un sous-programme est dit Récursifrécursif s’il
est, tout au moins en partie, défini par lui-même.
Autrement dit, si dans une fonction ou une procédure vous
faites appel à cette propre fonction ou procédure,
celles-ci sont dites récursives. L’exemple le
plus simple est la factorielle : n!=n*(n-1)!
Il existe deux types de récursivité :
-
Simple ou rapide :
le sous-programme s’appelle lui-même.
-
Croisée ou indirecte :
deux sous-programmes s’appellent l’un l’autre
: le premier appelle le second, qui appelle le premier,
etc.
La récursivité peut être
appliquée tant aux fonctions qu’aux procédures.
Pour une récursivité simple
:
Procédure recursive()
Début
/* instructions */
recursive()
/* instructions */
Fin
Pour une récursivité croisée
:
Procédure recur1()
Début
/* instructions */
recur2()
/* instructions */
Fin
Procédure recur2()
Début
/* instructions */
recur1()
/* instructions */
Fin
La suite ne va exposer que les sous-programmes
récursifs simples.