Présentation

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 compris les 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 à ajouter 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, sub xxx, endsub, etc., sub pour sous-programme).

Lorsqu’un programme est très long, il n’est pas réaliste de tout programmer d’un seul tenant. Le programme est décomposé en de plus petites unités ou parties réutilisables qui sont ensuite appelées au 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...

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

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 :

10!=10*9*8*7*6*5*4*3*2*1
Donc 10!=10*(9*8*7*6*5*4*3*2*1)
Donc 10!=10*9!
Donc n!=n*(n-1)!

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 
Début 
  nfact(n-1) 
  Retourne n 
Fin

Cette fonction n’est pas complète car elle va s’exécuter à l’infini....

Exercices

Exercice 1

Créer une fonction calculant la somme de valeurs passées en paramètre. Cette fonction aura le résultat comme premier paramètre par référence et le tableau de valeurs en deuxième paramètre. Appeler la fonction avec un tableau contenant les nombres 5,9,4 et 18. Écrire la solution en PHP.

Exercice 2

Créer un tableau contenant 10 chiffres aléatoires entre 1 à 100 puis trier celui-ci sans utiliser les méthodes de tri de tableau comme sort(). Il faudra créer une fonction pour échanger deux valeurs dans un tableau. Afficher ces valeurs séparées par une virgule. Écrire la solution en PHP.

Exercice 3

Créer une fonction pour afficher une phrase contenant de manière aléatoire un nombre quelconque de mots passés en paramètre. Chaque mot ne doit apparaître qu’une seule fois. La fonction prendra un tableau en paramètre. Écrire la solution en PHP.

Exercice 4

Soit le tableau A avec les éléments 3,8,15,16. Créer un tableau B à l’aide d’une boucle contenant tous les éléments de 1 à 20 sauf les éléments du tableau A. Créer une fonction qui calcule le cube de ce chiffre et afficher dans un tableau HTML les éléments du tableau B dans une première colonne et le cube des éléments de...