Table des matières

1 Fonctions et procédures 2
1 Diviser pour régner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1 Avantages de la technique . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Procédure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Représentation algorithmique . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Fonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1 Représentation algorithmique . . . . . . . . . . . . . . . . . . . . . . 6
4 Avantages de procédures et fonctions . . . . . . . . . . . . . . . . . . . . . . 7
5 Passage de paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.1 Passage par valeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.2 Passage par adresse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.3 Comparaison entre les deux passages . . . . . . . . . . . . . . . . . . 8
5.4 Exemple de passage de paramètres . . . . . . . . . . . . . . . . . . . 8
5.5 Avantages et inconvénients des deux méthodes . . . . . . . . . . . . . 9
6 Portée de Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.1 Variable locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.2 Variable globale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7 La récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8 Les trois règles de la récursivité . . . . . . . . . . . . . . . . . . . . . . . . . 12
9 Solution Récursive vs itérative . . . . . . . . . . . . . . . . . . . . . . . . . . 13
10 Récursion terminale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
11 Structure de données récursive . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1
Chapitre 1

Fonctions et procédures

La résolution de problèmes est plus facile quand on décompose en sous problèmes, ainsi
la complexité de se réduit par cette décomposition, si la complexité persiste, on continuera
la décomposition jusqu’à ce que tous les sous problèmes deviendront facile à résoudre. On
appelle le processus de décomposition affinement successive du problème à résoudre et en pro-
grammation, on appelle programmation procédurale, dans la suite les sous problèmes seront
résolus par un concept particulier appelé sous programme, routine ou fonction, ce concept
sera détaillé dans ce chapitre et illustré par des exemples.

1 Diviser pour régner

En informatique, diviser pour régner est un paradigme de conception d’algorithme basé
sur la récursion. Un algorithme fonctionne en décomposant récursivement un problème en
deux ou plusieurs sous-problèmes jusqu’à ce qu’ils deviennent assez simples pour être réso-
lus directement. Les solutions aux sous-problèmes sont ensuite combinées pour donner une
solution au problème initial.
Cette technique est à la base d’algorithmes efficaces pour toutes sortes de problèmes,
tels que les algorithme de tri (par exemple : tri rapide, fusion...), en multipliant de grands
nombres (par exemple, l’algorithme de Karatsuba, en trouvant le plus court chemin, l’analyse
syntaxique et le calcul de transformée de Fourier discrète).
La compréhension et la conception des algorithmes diviser pour régner est une compé-
tence complexe qui nécessite une bonne compréhension de la nature du problème sous-jacent
à résoudre. Comme pour prouver un théorème par induction, il est souvent nécessaire de
remplacer le problème d’origine par un problème plus général ou compliqué afin d’initiali-
ser la récursivité, et il n’existe pas de méthode systématique pour trouver la généralisation
appropriée. Ces complications sont observées lors de l’optimisation du calcul d’un nombre
Fibonacci avec double récurrence efficace.
L’exactitude d’un algorithme suivant diviser pour régner est généralement prouvée par
une induction mathématique, et son coût de calcul est souvent déterminé en résolvant les
relations récurrentes.

2
1.1 Avantages de la technique
Résolution de problèmes difficiles
La technique diviser pour régner est un outil puissant pour résoudre des problèmes dif-
ficiles conceptuellement : tout ce qu’il faut, c’est une façon de partitionner le problème en
sous-problèmes, de résoudre les cas triviaux et de combiner les sous-problèmes avec le pro-
blème initial. De même, diviser pour régner nécessite seulement de réduire le problème à des
problèmes plus petits qui soient faciles à résoudre, comme le problème de tour de hanoï, qui
réduit le déplacement d’une tour de hauteur n pour déplacer une tour de hauteur n − 1.

Efficacité de l’algorithme
Le paradigme diviser pour régner contribue souvent à la découverte d’algorithmes effi-
caces. Par exemple, c’était la clé de la méthode de multiplication rapide de Karatsuba, des
algorithmes de tri rapide et tri par fusion, l’algorithme de Strassen pour la multiplication
matricielle et les transformées de Fourier rapides.
Dans tous ces exemples, l’approche diviser pour régner a permis une meilleur amélioration
du coût asymptotique de la solution.

Parallélisme
Les algorithmes de type diviser pour régner sont naturellement adaptés pour être exécutés
dans des machines multiprocesseurs, en particulier des systèmes de mémoire partagée où la
communication de données entre processeurs n’a pas besoin d’être planifiée à l’avance, car
des sous-problèmes distincts peuvent être exécutés sur différents processeurs.

Accès à la mémoire
Les algorithmes utilisant la technique diviser pour régner ont tendance à utiliser effica-
cement les caches de mémoire. La raison en est qu’une fois qu’un sous-problème est assez
petit, il est possible, en principe, de résoudre tous ses sous-problèmes dans le cache, sans
avoir accès à la mémoire secondaire qui est plus lente. Ses algorithmes peuvent être conçus
pour des algorithmes importants (par exemple :algorithme de tri, TFF et multiplication ma-
tricielle) pour rendre des algorithmes optimaux de cache ; ils utilisent le cache d’une manière
probablement optimale, dans un sens asymptotique, indépendamment de la taille du cache.
Le même avantage existe concernant les autres systèmes de stockage hiérarchiques, tels que
NUMA (non uniform memory access) ou mémoire virtuelle, ainsi que pour plusieurs niveaux
de cache : une fois qu’un sous-problème est assez petit, il peut être résolu dans un niveau
donné de la hiérarchie, sans accéder aux niveaux supérieurs (plus lents).

2 Procédure
Une procédure est un ensemble d’instructions décrivant une action simple ou composée
permettant en générale de résoudre un problème élémentaire, identifiée par un nom et qui
peut avoir zéro à plusieurs résultats.

3
2.1 Représentation algorithmique
Algorithme 1 : Représentation algorithmique de procédure
1 Algorithme nom_algo ;
2 Var variables ;
3 Procédure nom_procédure(liste de paramètres : type) ;
4 variables ;début
5 Instructions ;
6 Fin
7 début
8 Instructions et appel de procédure ;
9 fin

— On appel la ligne 03 ( commençant par Procédure) l’entête de la procédure, elle est

identifiée par un nom et peut avoir un à plusieurs paramètres ou non.
— Les paramètres de la procédure sont vus comme une interface qui communique avec
l’extérieure et les autres routines (procédures ou fonctions).
— L’appel de la procédure se fait dans la partie principale de l’algorithme ou dans une
autre procédure ou fonction qui doit être définie après la procédure en question.
— Les paramètres de la procédure ne doivent jamais être lus à l’intérieur de la procédure
sans que l’énoncé ne l’indiqué.
— L’ordre et le nombre de paramètres d’entrées ou de sorties doit être respecté lors de
l’appel.

Exemple 1 : Procédure avec paramètres

Algorithme 2 : Procédure avec paramètres

1 Algorithme Somme_nombres ;
2 Var x,y : entier ;
3 Procedure Addition(a,b : entier) ;
4 var Som :entier
5 début
6 Som ← a+b ;
7 Afficher(Som) ;
8 Fin
9 début
10 Afficher(’donner un nombre entier :’) ;
11 lire(x) ;
12 Afficher(’donner un nombre entier :’) ;
13 lire(y) ;
14 Addition(x,y) ;
15 fin

4
 — Cet exemple illustre un algorithme qui permet de additionner deux nombres entiers
en utilisant la procédure Addition, cette à deux paramètres a et b en entrée, elle fait
l’addition de deux nombres affecté à Som et l’affiche.
— Dans le corps principal de l’algorithme, On lit les deux variables x et y et on appelle la
procédure par son nom (les règles de nommage de la procédure est les même que celle
de variable) ce qui permet d’avoir le résultat de cette procédure qui est affiché x+y.
— Notant que les variables utilisées dans la procédure sont diffèrent de celles dans le corps
de l’algorithme, se qui fait qu’on utilise l’entête a procédure comme interface entre le
corps de l’algorithme et la procédure.

Exemple 2 : procédure sans paramètres

Algorithme 3 : Procédure sans paramètres

1 Algorithme Dessin_ligne ;
2 début
3 ligne() ;
4 fin

— Dans cette exemple la procédure ligne est sans paramètres d’entrée elle affiche 15 fois
le chaîne ’–’.
— l’appel de cette procédure dans le corps de l’algorithme se fait juste par son nom.

2.2 Exercice
Soit l’algorithme suivant :

1 Algorithme Tableau ;
2 type Tab=Tableau [1..5] de Entier ;
3 Var T :Tab ;
4 i : entier ;
5 début
6 pour i ← 1, 5 faire
7 lire(T[i]) ;
8 FinPour
9 pour i ← 1 , 5 faire
10 afficher(T[i]) ;
11 FinPour
12 fin

1. Essayer de décomposer cet algorithme en terme de fonctionnalités.

2. En se basant sur la question précédente. Transformer cet algorithme en un algorithme
composé de procédure.

5
3 Fonction
Une fonction est un cas particulier de la procédure qui retourne un seul paramètre de
type simple (entier, caractère, réel...) ou bien de type pointeur. Toute fois, il est obligatoire
de préciser, dés le début le type de la fonction qui est en même temps le type du résultat
à retourner. Comme la procédure, elle est identifiée par un nom, peut être sans ou un à
plusieurs paramètres et elle retourne un seul résultat de type simple.

3.1 Représentation algorithmique

Algorithme 4 : Représentation algorithmique de fonction
1 Algorithme nom_algo ;
2 Var Variables ;
3 Fonction nom_fonction(liste de paramètres :type) :type ;
4 variables ;
5 début
6 Instructions ;
7 return(valeur) ;
8 Fin
9 début
10 Instructions et appel de fonction ;
11 fin

Exemple 01 : Fonction de somme de deux nombres

Algorithme 5 : Somme de deux nombres en utilisant une fonction
1 Algorithme Somme ;
2 Var A, B, C : entier ;
3 Fonction Addition(X,Y :entier) :entier ;
4 début
5 return(X+Y) ;
6 Fin
7 début
8 Afficher(’donner un nombre entier :’) ;
9 lire(A) ;
10 Afficher(’donner un nombre entier :’) ;
11 lire(B) ;
12 C ← Addition(A,B) ;
13 Afficher(C) ;
14 fin

Pour la fonction addition, elle a deux paramètres d’entrées X, Y de type entier, et

retourne une valeur qui est égale à la somme de deux nombres. En début de l’algorithme, en
lit les deux valeurs A et B, C prend le résultat retourné par la fonction Addition.

6
Exemple 02 : Fonction de somme de n nombres
Algorithme 6 : Somme de n nombres en utilisant une fonction
1 Algorithme Somme_n_nombres ;
2 Var n, B, C : entier ;
3 Fonction Somme(X :entier) :entier ;
4 var Som, i : entier ;
5 début
6 Som ← 0 ;
7 Fin
8 pour i ← 1, X faire
9 Som ← Som +i ;
10 fin
11 return(Som) ;
12 début
13 Afficher(’donner un nombre entier :’) ;
14 lire(n) ;
15 C ← Somme(n) ;
16 Afficher(C) ;
17 fin

4 Avantages de procédures et fonctions

— Éviter la répétition du code ou des instructions, ainsi, on obtient un code réutilisable.
— Rendre la compréhension du code facile et mieux lisible.
— Rendre la maintenance plus facile, puisque on peut détecter l’erreur rapidement et de
corriger sans difficultés.
— Modification et évolution facile : On peut ajouter d’autres fonctionnalités facilement
et sans que la complexité augmente.
— Optimiser le nombre d’instructions dans un algorithme.

5 Passage de paramètres
Il existe deux méthodes pour passer des variables en paramètre dans une fonction ou
procédure : le passage par valeur et le passage par adresse.

5.1 Passage par valeur

La valeur de des variables est passée en paramètre est copiée dans les variables locales.
C’est les valeurs des variables qui sont utilisée pour faire les calculs dans la fonction appelée.
Dans ce type de passage la variable locale dans la fonction appelée ne modifie la variable
passée en paramètre, parce que ces modifications ne s’appliquent qu’à une copie de cette
dernière.

7
5.2 Passage par adresse
La deuxième technique consiste à utiliser les variables elles-mêmes. Il n’y a donc plus
de copie, plus de variable locale. Toute modification du paramètre dans la procédure ou
fonction appelée entraînera la modification directe de la variable passée en paramètre. Pour
représenter le passage par adresse, on utilise le mot var ce qui signifie que la variable est
passé par adresse et donc elle est modifier.

5.3 Comparaison entre les deux passages

Passage par valeur
— Les paramètres locaux sont des copies des arguments originaux transmis
— Les modifications apportées à la fonction dans ces variables n’affectent pas les originaux

Passage par adresse

— Les paramètres locaux font référence aux emplacements de stockage des arguments
originaux transmis.
— Les modifications apportées à ces variables dans la fonction affecteront les originaux
— Aucune copie n’étant faite, le temps système de copie (temps, stockage) est exclu.

5.4 Exemple de passage de paramètres

Prenant un exemple classique qui est la permutation de deux variables illustré dans
l’algorithme 7.

8
 Algorithme 7 : Passage par adresse et par valeur
1 Algorithme algo_permut ;
Var : X,Y :entier ;
2
3 Procédure permute_1(a,b : entier) ;
4 var c :entier ;
5 début
6 c ← a;
7 a ← b;
8 b ← c;
9 Fin
10 Procédure permute_2(var a,b : entier) ;
11 var c :entier ;
12 début
13 c ← a;
14 a ← b;
15 b ← c;
16 Fin
17 début
18 Afficher(’Donner un nombre entier :’) ;
19 lire(X) ;
20 Afficher(’Donner un nombre entier :’) ;
21 lire(Y) ;
22 Permute_1(X,Y) ;
23 Afficher(X,Y) ;
24 Permute_2(X,Y) ;
25 Afficher(X,Y) ;
26 fin
Dans cet algorithme, on a défini deux procédures permut_1 et permut_2 qui sont tous
les deux utilisées dans le corps principal de l’algorithme, on remarque que la déférence entre
les deux procédures est dans l’entête de la procédure permut_2 ou on a ajouté au variables
a et b le mot clé var.
Après le déroulement de l’algorithme, on affecte deux valeurs à partir du clavier, X=5 et
Y=10, après l’exécution de la ligne 22 on remarquera que les valeurs de X et Y ne changent
pas ce qui est confirmé par l’affichage, alors qu’après l’exécution de la ligne 24 les valeurs de
X et Y changent. Le premier cas on a fait un passage par valeur et le deuxième un passage
par adresse.

5.5 Avantages et inconvénients des deux méthodes

— Le passage par adresse est plus rapide et plus économiques en mémoire que le passage
par valeur, puisque les étapes de la création de la variable locale et la copie de la valeur
ne sont pas faites. Il faut donc éviter le passage par valeur dans les cas d’appels récursifs
de fonction ou de fonctions travaillant avec des grandes structures de données.

9
 — Les passages par valeurs permettent d’éviter de détruire par mégarde les variables
passées par adresse. L’utilisation de constantes permet de prévenir la destruction acci-
dentelle des paramètres passés par adresse. Le compilateur interdira alors toute modifi-
cation de la variable dans la fonction appelée, ce qui peut parfois obliger cette fonction
à réaliser des copies de travail en local.

6 Portée de Variables
6.1 Variable locale
Un variable locale est une variable qui ne peut être utilisée que dans la fonction ou la
procédure où elle est définie.
Elle s’oppose à la variable globale qui peut être utilisée dans tout l’algorithme ou le
programme.
Selon le langage utilisé, une variable locale à une fonction sera accessible ou non aux
fonctions que celle-ci appelle (notion de portée d’une variable).

6.2 Variable globale

La variable globale est une variable déclarée à l’extérieur du corps de toute fonction
ou procédure, et pouvant donc être utilisée n’importe où dans l’algorithme ou programme.
(également appelée variable de portée globale).

Exemple : Dans l’algorithme 2 les variables a et b sont définit dans la procédure Addition
et donc sont des variables locales de la procédure, alors que les variables x et y sont dites
globales puis qu’elles sont visibles dans tout l’algorithme même dans la procédure. plus
précisément, Si on veut afficher les variables a et b dans le corps principal de l’algorithme,
on obtient une erreur que les variables ne sont pas déclarées, contrairement à x et y, elles
peuvent être affichées n’importe ou dans l’algorithme.

7 La récursivité
La récursivité est une méthode de résolution de problèmes qui consiste à décomposer un
problème en sous-problèmes de plus en plus petits jusqu’à obtenir un problème suffisamment
simple à résoudre de manière triviale. Elle implique généralement une fonction qui s’appelle
elle-même. Bien que cela puisse sembler peu superficiel, la récursivité permet d’écrire de
solutions élégantes à des problèmes qui pourraient être très difficiles à résoudre en utilisant
la solution itérative.
En d’autres terme un algorithme est dit récursif s’il s’appelle lui-même. Les langages
de programmation tels que LISP et Algol 60 ont été parmi les premiers qui ont introduit
la récursivité, maintenant, tous les langages de programmation modernes proposent une
implémentation de la récursivité.
La récursivité c’est l’application de la technique "Diviser pour régner" ( divide to conquer)
à l’algorithmique : pour résoudre un problème d’une taille donnée, on scinde ce problème

10
en plusieurs sous-problèmes plus petits, on recommence avec chacun de ces sous-problèmes
jusqu’à ce que tous les petits sous-...-sous-problèmes soient facile à résoudre.
En général, les programmes informatiques récursives nécessitent plus de mémoire et de
temps de calcul par rapport les algorithmes itératifs, mais ils sont plus simples à concevoir
et dans de nombreux cas un moyen naturel de réfléchir à la résolution de problèmes.

Exemple 01 : On veut calculer la somme de n nombres. Dans cet exemple, un des pro-
blèmes classiques que nous avons déjà résolu avec la solution itérative et sans recourir à la
récursivité. Supposons qu’on souhaite calculer la somme d’une suite de nombres tels que :
1..7. Une fonction itérative qui calcule la somme et affiche le résultat ,illustré par algorithme
6, cette fonction utilise une variable d’accumulation Som qui permet d’accumuler tous les
nombres de la suite en commençant par 1 et en ajoutant à chaque fois à la somme du nombre
incrémenté de un. Supposant maintenant que nous ne voulons pas utiliser de boucle ? ! ! ! On
peut observer que :
— Somme(n) = n+ Somme(n-1)
— Ainsi que, somme(n-1) = n-1 +Somme(n-2)
— ...
— Si on atteint 1, la fonction somme retournera la valeur 1
— On résumant cette observation

Somme(n) = n + (Somme(n − 1 + Somme(n − 2 + Somme(n − 3... + Somme(1)))))

Somme(1) retourne 1, et donc la somme se fait à l’envers

La technique décrite illustre le concept de la récursivité. Elle consiste à réduire le calcul
par des appels successive de la fonction elle même vers un cas simple, dans cet exemple 1,
puis rassemblé la solution à un sens inversé. La solution récursive du problème illustré dans
l’algorithme 8 est comme suit :

11
 Algorithme 8 : somme de n nombres en utilisant une fonction
1 Algorithme Somme_n_nombres ;
Var : n, B, C : entier ;
2 Fonction Somme(X :entier) :entier ;
3 var Som, i : entier ;
4 début
5 Si X = 1 alors
6 Return(1)
7 Sinon
8 Return(n+Somme(n-1)) ;
9 FinSi
10 Fin
11 début
12 Afficher(’donner un nombre entier :’) ;
13 lire(n) ;
14 C ← Somme(n) ;
15 Afficher(C) ;
16 fin

8 Les trois règles de la récursivité

Pour une meilleur utilisation de la récursivité en algorithmique et en programmation, les
algorithmes récursifs doivent obéir à trois lois importantes :
1. Un algorithme récursif doit avoir un cas de base.
2. Un algorithme récursif doit changer son état et de progresser vers le cas de base.
3. Un algorithme récursif doit se appeler, de manière récursive.
On peut vérifier chacune de ces conditions et voir si elles sont respectées dans l’algorithme 8.
Tout d’abord, le cas de base est la condition qui permet à la fonction d’arrêter la récursivité.
Un cas de base est typiquement un problème qui est assez petit qui permet de retourner
une valeur directe ment. Dans l’algorithme précédent le cas de base est lorsque n = 1 et la
somme de 1 retourne 1.
Pour vérifier la deuxième condition, on vérifie que pour chaque changement d’état, la
fonction conduit vers le cas de base. Un changement d’état signifie que certaines instructions
influent directement la variable de la récursion et la réduit vers le cas de base. Habituellement
la variable que présentes notre problème devient de plus en plus petit et se réduit vers 1. la
progression de la variables X se réduit automatiquement vers le cas de base et donc l’arrêt
de l’appel récursif de la fonction somme. C’est exactement ce qui se passe dans instruction
lorsque n 6= 1 on appel la fonction somme avec n plus la somme de n − 1 (Somme(n) =
n + Somme(n − 1)).
La troisième condition est évidement vérifiée, puisque la fonction s’appelle elle même
dans son corps.

12
Exercice 01 : Écrire une fonction récursive qui permet de calculer le factoriel d’un nombre
entier positif.

9 Solution Récursive vs itérative

Pour mettre en oeuvre des algorithmes récursifs nécessite le plus souvent une pile. Vue
la difficulté d’implanter cette pile qui a fait dire pendant longtemps que les programmes
récursifs étaient moins efficaces que les programmes itératifs, mais la situation a changé. En
fait, le débat sur le choix entre la récursivité ou l’itératif est aussi vieux que l’informatique et
les progrès des compilateurs réduit encore la différence d’efficacité. Voici quelques arguments
en faveur de la récursivité :
— La récursion permet de présenter simplement des algorithmes beaucoup plus astucieux
(et donc plus efficaces) (exemple l’algorithme de tri rapide).
— Les compilateurs d’aujourd’hui sont tellement astucieux que plus le programme leur
est présenté de façon abstraite et sans effets de bord, plus ils peuvent mettre en oeuvre
leurs optimisations et aboutir à des codes objets efficaces.
— Des structures de données récursives, comme par exemple les quadtrees (arbre qua-
ternaire), ont été conçues pour leur efficacité. On ne voit pas comment on pourrait
exécuter sur elles des algorithmes non récursifs.

10 Récursion terminale
On dit qu’un algorithme est terminal, si les valeurs de retour sont soit des constantes,
soit des valeurs directement issue d’un appel récursif, sans aucune autre modification ou
opération. Dans le cas contraire, il sera dit non-terminal. Cette notion est importante si l’on
veut déterminer une version itérative de l’algorithme concerné. Dans l’ exemple précédent,la
fonction factoriel est non terminal car, bien que le cas d’arrêt renvoie une constante, celui
de l’appel récursif quant à lui modifie la valeur renvoyée en la multipliant par n avant de lui
même renvoyer une valeur

Exemple : Comme on a vu la fonction factoriel n’est pas une fonction récursive terminale.
Il existe une solution de tel façon que la fonction factoriel soit terminale, l’algorithme 9
illustre cette solution.

13
 Algorithme 9 : somme de n nombres en utilisant une fonction
1 Algorithme Fact ;
Var : n, B, C : entier ;
2 Fonction Factoriel(n :entier, i : entier ) :entier ;
3 var Som, i : entier ;
4 début
5 si X = 0 alors
6 Return(i)
7 sinon
8 Return(factoriel(n-1, n*i))
9 fin
10 Fin
11 début
12 Afficher(’donner un nombre entier :’) ;
13 lire(n) ;
14 Afficher(factoriel(n, 1) ;
15 fin

Cette solution est traduite en langage C par le code suivant :

1 # include < stdio .h >
2 unsigned factTR ( unsigned int n , unsigned int a )
3 {
4 if ( n == 0) return a ;
5
6 return factTR (n -1 , n * a );
7 }
8 // Fonction main
9 int main ()
10 {
11 int n ;
12 printf ( " Donner un nombre entier positif : " );
13 scanf ( " % u " ,& n );
14 printf ( " fatoriel (% u )=% u " ,n , factTR (n ,1));
15 return 0;
16 }

11 Structure de données récursive

Une structure de donnée récursive S est une structure qui se compose elle même d’une
structure de donnée S, ou si l’un de ses composantes est une structure de donnée faisant
appel à S. Parmi les structures de données récursives qu’on va explorer dans le troisième
chapitre, nous verrons les listes, les piles et les files.

14