Les sous-programmes

Procédures et fonctions

Vous êtes encore en train d’apprendre à modéliser votre pensée en informatique avec des problèmes assez simples et dans ce chapitre vous allez aller un plus loin dans votre réflexion. Imaginez un programme comme un logiciel de vidéo à la demande ou encore un client de messagerie ? Ne pensez-vous pas que ces programmes contiennent des millions, voire des milliards d’instructions ? Comment donc se retrouver facilement dans cette nuée d’instructions ?

Une première réponse est assez simple : découpez votre logique en petites parties qui seront appelées à la demande. Cette découpe permet de fortement réduire la complexité du programme en se focalisant uniquement sur des sous-problèmes plus simples à résoudre. Ces parties sont les sous-programmes qui seront appelés dans le programme principal, le point d’accès de l’application, comme le représente la figure suivante.

Programme principal et sous-programmes

En algorithmie, les sous-programmes se déclarent avant le programme comme suit :

SOUS-PROGRAMME sous_prog_A  
VAR  
   ... 
DEBUT  
   ... 
FIN  
PROGRAMME principal  
VAR  
   ... 
DEBUT  
   ...  
   sous_prog_A 
FIN 

En réalité, un programme n’est que rarement composé d’une seule série d’instructions qui s’enchaînent les unes après les autres. Pour pouvoir créer et maintenir correctement une application, les développeurs décomposent toujours le programme principal en plusieurs sous-programmes qui vont être appelés par ce dernier. Les sous-programmes représentent en fait une petite fonctionnalité du programme. Ils peuvent également s’appeler entre eux pour définir une hiérarchie de tâches.

Prenons comme exemple un jeu simple : le jeu du pendu. Décomposons-le en termes de fonctionnalités :

L’élégance de la récursivité

Par définition, un sous-programme récursif est un sous-programme qui s’appelle lui-même.

L’objectif de la récursivité est de simplifier, en théorie, un traitement complexe contenant des itérations, en écrivant uniquement des traitements simples. Cependant, il existe toujours un fossé entre la théorie et la pratique.

Regardons un peu l’évolution des langages de programmation avec beaucoup de vulgarisation. Les premiers langages de programmation, et encore certains exotiques de nos jours, n’implémentaient pas les structures itératives, seulement les conditionnelles. Comment faire alors pour répéter une instruction ?

Simplement en rappelant le sous-programme contenant cette instruction dans une conditionnelle, jusqu’à ce que la condition d’arrêt de l’itération, mise donc dans la condition du SI, soit juste.

Modélisons ce principe avec l’affichage d’un tableau.

Pour afficher un tableau, nous devons le parcourir du premier élément au dernier. Nous devons donc nous arrêter après l’affichage de ce dernier élément. Ainsi notre condition d’arrêt est "nous avons traité le dernier élément".

Un parcours de tableau se fait grâce à un compteur qui s’incrémente au fur et à mesure du parcours. Nous pouvons donc modéliser notre condition d’arrêt ainsi : le compteur doit être supérieur à la taille du tableau. Si j’ai traité le dernier élément du tableau je m’arrête, c’est-à-dire le compteur est arrivé à la taille du tableau.

Il existe plusieurs types de récursivités : la simple, la multiple, la croisée et l’imbriquée. Nous n’aborderons dans ce chapitre que les deux premiers types et nous laissons le lecteur aller plus loin par lui-même pour les deux derniers. Ces différents types de récursivités sont tous basés sur le même principe que la récursivité simple, seule la hiérarchie des appels récursifs change.

Algorithmes avancés sur les tableaux

L’objectif principal de l’informatique est de simplifier les traitements complexes pour l’utilisateur. Il va donc de soi que lorsqu’un programme travaille sur des tableaux, saisis par l’utilisateur ou non, il doive trier ces tableaux pour en faciliter les manipulations et donc les recherches.

Maintenant que nous avons étudié les sous-programmes et la récursivité, nous pouvons voir comment effectuer ces tris en partant des algorithmes les plus simples pour l’être humain, donc les moins performants pour la machine, aux plus optimisés pour l’ordinateur, donc les moins simples pour le cerveau humain (sous-entendu utilisant des sous-programmes récursifs).

PROCEDURE echanger(E/S : x, y : ENTIER)  
VAR  
   tmp : ENTIER  
DEBUT  
   tmp <- x  
   x <- y  
   y <- tmp  
FIN 

2. Tri par sélection

Le tri par sélection est le tri ayant la logique la plus simple. Nous commençons par chercher la plus petite valeur du tableau et nous la plaçons à la première case en décalant les autres cases, comme le montre la figure ci-après. Il ne nous reste plus qu’à appliquer les mêmes opérations sur le sous-tableau commençant à la case 2, puis celui commençant à la case 3, etc. jusqu’à arriver à un dernier sous-tableau de taille 1, ce qui indique que le tableau est bien trié.

Tri par sélection

Le tri par sélection demande donc deux manipulations :

• Trouver la plus petite valeur.

• Échanger la case courante avec la première case du sous-tableau correspondant. 

Nous avons donc besoin d’un sous-programme pour rechercher la plus petite valeur, ou plutôt l’indice de la plus petite valeur d’un tableau.

FONCTION indice-minimum (tab : TABLEAU[] : ENTIER, début, 
taille : ENTIER) : ENTIER  ...

Fonctions et procédures avec Python

Comme nous l’avons remarqué dans la section précédente, le Python n’implémente que les fonctions.

if __name__ == '__main__': 

# une fonction sans corps  
def maFontion():  
   pass  
  
# code pour la procédure affiche_tableau  
def afficheTableau(tab):  
   for e in tab:  
      print(e)  
  
# code de la procédure double  
def double(a):  
   return a * a  
  
# code de la fonction maximun  
def maximun(a,b):  
   if a > b :  
      return a  
   else:  
      return b  
  
# programme principal  
if __name__ == '__main__':  
   afficheTableau([1,2,3])  
   a...

Exercices