Security-X

Forum Security-X => Programmation => Cours => Discussion démarrée par: XmichouX le septembre 27, 2011, 09:35:39

Titre: Les fonctions : par itération et par récursion
Posté par: XmichouX le septembre 27, 2011, 09:35:39
Les Fonctions

Comme dans tous les langages, on utilise des fonctions.

Une fonction est un traitement (bloc d'instructions) que l'on peut utiliser n'importe où dans un programme : dans le main(), dans une fonction, etc. Le main() dans lequel on écrit tout notre code (à ce stade du cours) est la fonction principale du programme.

Une fonction est caractérisée par plusieurs choses en C :
- son nom,
- son type de retour,
- le type de ses paramètres (il peut ne pas y en avoir).

Toutes ces informations forment ce qu'on appelle le prototype d'une fonction, très utile au compilateur.

Au lieu de réécrire et d'adapter à chaque fois un traitement dans le code, on va appeler une fonction qui contient déjà le code voulu. Et pour la rendre modulable (adaptable à différentes valeurs, conditions, etc.), on peut lui passer des paramètres, afin qu'elle puisse effectuer un traitement sur des donnés dynamiques, et non statiques.

Nous allons commencer par prendre un exemple avec le calcul d'une factorielle. Rappel = 5! = 5x4x3x2 = 120.

#include <stdio.h>

int main () {
        int nb_factorielle = 8, i, resultat = nb_factorielle;

for (i = nb_factorielle -1; i > 0; i--) {
resultat = resultat * i;
}
printf ("Le resultat est %i\n", resultat);
}

Bien. Mais maintenant, si on faisait un programme qui demande à l'utilisateur de taper un nombre et qui calcule la factorielle (et ce, un grand nombre de fois), il serait très fastidieux de réécrire le code à chaque fois, en l'adaptant, et cela rendrait surtout le programme beaucoup plus long et moins lisible. Pour cela, on va utiliser une fonction, à l'instar de ln(), cos(), ... en mathématiques.

Voici, ce que cela donne :

#include <stdio.h>

unsigned int factorielle (int nombre) {
int i;
unsigned int resultat = nombre;

if (nombre ==  0)
return 1;

for (i = nombre -1; i > 0; i--) {
resultat = resultat * i;
}
return resultat;
}

int main () {
int nombre_tape = 0;

while (nombre_tape >= 0) {
printf ("Tapez vote nombre : ");
scanf ("%d", &nombre_tape);
if (nombre_tape >= 0)
printf ("La factorielle de %d est egale a %u\n", nombre_tape, factorielle(nombre_tape));
}
return 0;
}

On voit la différence non ? Au lieu d'avoir tout le code pour calculer la factorielle dans le programme principal, on le condense dans une fonction qu'on appelle comme ceci : printf ("La factorielle de %d est egale a %u\n", nombre_tape, factorielle(nombre_tape));

On peut aussi tout à fait stocker le résultat de la fonction dans une variable et l'afficher ensuite. Ici, nous n'avions pas besoin de conserver cette information.

unsigned int resultat = factorielle(nombre_tape);
printf ("resultat : %u\n", resultat);

Ce qui est identique à :

unsigned int resultat;
printf ("La factorielle de %d est egale a %u\n", nombre_tape, resultat = factorielle(nombre_tape));

Ici, le prototype de la fonction est : unsigned int factorielle (int).
Elle est déclarée comme ceci :

int factorielle (int nombre) {
        ... instructions ....
}

Le nom de la fonction est factorielle, elle prend en paramètre un entier (int), dont le nom est nombre. Enfin, celle-ci retourne un entier (int).
Bref, le schéma est le suivant : Type_retour Nom_fonction (type_paramètre1 nom_paramètre1, type_paramètre2, nom_paramètre2, ....) {}

En C, on ne peut pas avoir plusieurs fonctions ayant le même prototype ou le même nom (testez, vous verrez).

On remarque que la fonction se trouve au-dessus du langage main, ce n'est pas au hasard. Si vous ne le faites pas, ça ne marchera pas : Arrivé à l'instruction d'appel de la fonction, le programme ne saura pas où se trouve votre fonction. Pour régler ce problème, il suffit de déclarer le prototype de notre fonction au préalable.
On déclare alors juste après les #include ce prototype : unsigned int factorielle (int);.

Si vous ne souhaitez pas que votre fonction retourne quelque chose de spécial, vous indiquez le type void pour le retour de la fonction.

Exemple :

#include <stdio.h>

void alerte();

int main () {
alerte();
}

void alerte () {
printf ("Attention, vous dépassez l'espace qui vous est autorisé.\n");
}

Fonctions itératives et récursives

Lors d'un traitement dans une fonction, on peut être amené à effectuer des traitements itératifs ou récursifs.
Itératif, c'est par exemple lancer une boucle avec un bloc d'instructions à l'intérieur.
Récursif, c'est lorsqu'une fonction s'appelle elle-même.

Revenons, la fonction factorielle que nous avons étudié plus haut est une fonction itérative. Voyons maintenant comment faire la fonction récursive correspondante.

#include <stdio.h>

unsigned int factorielle (int);

int main () {
int nombre_tape = 0;

while (nombre_tape >= 0) {
printf ("Tapez vote nombre : ");
scanf ("%d", &nombre_tape);
if (nombre_tape >= 0)
printf ("La factorielle de %d est egale a %u\n", nombre_tape, factorielle(nombre_tape));
}
return 0;
}

unsigned int factorielle (int nombre) {
if (nombre < 0)
return -1;
if (nombre == 0 || nombre == 1)
return 1;
unsigned int resultat = nombre;
return resultat * factorielle(nombre-1);

}

Cette fois-ci, la fonction est bien récursive, car elle s'appelle bien elle-même.
Pour que la fonction s'arrête et ainsi éviter des débordements de pile (stack overflow), il faut poser des conditions d'arrêt.
Pour une factorielle, on sait que 1! et 0! = 1. Lorsque le paramètre est donc 1 ou 0, on retourne directement la valeur 1. La récursivité s'arrêtera donc lorsque le nombre aura suffisamment diminué (-1 à chaque appel) pour atteindre 1 ou 0 : tous les return sont effectués et le retour final est rendu au programme principal : le résultat.

C'est à vous de juger, en fonction de vos besoins, quel type de fonction est le plus approprié. Pour des parcours d'arbres ou de graphes par exemple, les fonctions récursives peuvent s'avérer très utile.
Titre: Re : Les fonctions : par itération et par récursion
Posté par: igor51 le juillet 18, 2012, 22:06:11
UP !