Les sous-programmes

1. Principe

Lors de la présentation de la structure d’un algorithme, il a été brièvement abordé la possibilité d’ajouter une partie supplémentaire en début de programme, avant les déclarations des variables. Cette partie n’avait pas encore été abordée, alors qu’à ce niveau vous savez, si vous avez bien assimilé le contenu des chapitres précédents, déjà très bien programmer. Or peut-être avez-vous remarqué quelques limitations frustrantes, et notamment une certaine lourdeur lorsque le programme est très long et qu’il s’agit de répéter certains blocs d’instructions pourtant déjà présents ailleurs. Par exemple, rappelez-vous un simple petit programme qui calcule la valeur absolue d’une commande. L’embêtant est qu’à chaque fois que vous voulez calculer cette valeur, vous devez répéter la structure conditionnelle. N’aurait-il pas été plus simple de le faire une seule fois, et de passer à ce bloc d’instructions uniquement la valeur dont on veut récupérer la valeur absolue ?

Vous pourriez pour cela envisager un second programme qui serait lancé par le programme principal avec comme paramètre cette valeur. C’est techniquement faisable, mais placer un second programme à part (un exécutable) juste pour ce genre de traitement, c’est une perte de temps et d’espace.

L’autre solution consiste à rajouter le code nécessaire à ce programme dans une structure spéciale et à part du programme principal. C’est ce qu’on appelle un sous-programme. Les anciens langages BASIC utilisaient d’ailleurs des instructions en ce sens (gosub, subxxx, endsub, etc., sub pour sous-programme).

Lorsqu’un programme est très long, il n’est pas réaliste de le coder d’un seul tenant. Le programme est décomposé en de plus petites unités ou parties réutilisables qui sont ensuite appelées le moment opportun par le programme principal. Un sous-programme évite la répétition inutile de code et permet de clarifier le programme. Une fois tous les sous-programmes réalisés...

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é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é :

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.

2. Un premier exemple : la factorielle

Une factorielle est l’exemple rêvé d’application d’un algorithme récursif. Cet exemple a déjà été présenté dans les chapitres précédents mais un petit rappel s’impose :

Si vous créez une fonction (appropriée dans ce cas) appelée fact() et chargée de calculer la factorielle de n, vous auriez un raccourci de ce genre :

fact(n)=n*fact(n-1)
 

De là il vous devient très facile d’écrire une fonction fact() récursive :

Fonction fact(n:entier) :entier ...