Blog ENI : Toute la veille numérique !
💥 Un livre PAPIER acheté
= La version EN LIGNE offerte pendant 1 an !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. Algorithmique - Techniques fondamentales de programmation
  3. Techniques fondamentales de programmation
Extrait - Algorithmique - Techniques fondamentales de programmation exemples en C# - (nombreux exercices corrigés) [BTS - DUT informatique]
Extraits du livre
Algorithmique - Techniques fondamentales de programmation exemples en C# - (nombreux exercices corrigés) [BTS - DUT informatique]
1 avis
Revenir à la page d'achat du livre

Les sous-programmes

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

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

Exercices

Exercice 1

Créer la fonction absolu qui prend une valeur numérique en paramètre et qui retourne sa valeur absolue.

Exercice 2

Reprendre l’algorithme de l’exercice 4 du chapitre Les tableaux et structures et le transformer en fonction qui trie le tableau passé en paramètre. Un second paramètre, de type booléen, sera vrai pour croissant, faux pour décroissant. Pour simplifier la tâche, on introduit la fonction prédéfinie taille() qui retourne le nombre d’éléments du tableau.

Le tri par ordre décroissant a-t-il un intérêt ?

Exercice 3

Recherchez dans la documentation C# si des fonctions prédéfinies existent pour trier un tableau d’entiers. Quel est l’intérêt de le programmer soi-même ?

Exercice 4

Écrire une fonction qui calcule les nombres de Fibonacci jusqu’à n (entier) de manière récursive. Les nombres de Fibonacci sont issus d’une suite : Fn+2 = Fn+1 + Fn. Les deux premiers termes sont connus : F0=0 et F1=1. Donner le résultat en C#.

Exercice 5

Écrire les fonctions Pair et Impair qui prennent comme paramètre un entier et qui retournent VRAI ou FAUX selon le cas.

Modifier ensuite les fonctions pour qu’elles s’appellent l’une et l’autre.