Les sous-programmes récursifs
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.