rcursivit .pdf


Nom original: rcursivit.pdf
Titre: Factoriel (n)
Auteur: SAYARI

Ce document au format PDF 1.7 a été généré par Soda PDF 5, et a été envoyé sur fichier-pdf.fr le 24/11/2013 à 08:44, depuis l'adresse IP 197.7.x.x. La présente page de téléchargement du fichier a été vue 538 fois.
Taille du document: 312 Ko (3 pages).
Confidentialité: fichier public


Aperçu du document


ALGO & PROG

PROF : Mohamed SAYARI

C
CHHAAPPIITTRREE 22 ::

LA RECURSIVITE
I.

Introduction :

1. Activité 1 :
1. Soit la définition de la fonction factoriel (module qui permet de calculer le factoriel d’un
nombre n positif)
Factoriel (5) = 5 * 4 * 3 * 2 * 1  Factoriel (n) = n * n-1 * n-2 * n-3 * …………… * 2 * 1
Factoriel (4) = 4 * 3 * 2 * 2 * 1  Factoriel (n-1) = n-1 * n-2 * n-3 * …………… * 2 * 1
Factoriel (n) = n * Factoriel (n-1)
2. Et soit la définition de la fonction inverse (module qui permet d’inverser une chaîne de
caractères .
Inverse ("ALGO") = "O" + inverse ("ALG")  Inverse (ch) = denier caractère + Inverse du reste de la chaîne
privé du dernier caractère
Inverse ("ALG") = "G" +inverse ("AL")  Inverse (ch) = denier caractère + Inverse du reste de la chaîne
privé du dernier caractère
Inverse (ch) =ch[Long(ch)] + inverse (sous-chaîne (ch, 1, Long(ch)-1))
Constatation 1 :
Dans toutes les activités précédentes, nous avons utilisés, pour définir un module, le module lui
même avec différents paramètres :
Factoriel (n) = Factoriel (n-1)
Inverse(ch) = ch[ L] + inverse (sous-chaîne (ch, 1, L-1))
Lorsqu’un module (fonction ou procédure) s’appelle lui-même : ce procédé sera appelé récursivité
et le module est dit module récursif.

II. Définition :
-

Un programme récursif est un module qui s’appelle lui-même.

- La récursivité permet de résoudre certains problèmes d'une manière très rapide,
alors que si on devrait les résoudre de manière itérative, il nous faudrait
beaucoup plus de temps et de structures de données intermédiaires.

III. Principe et Présentation d’une solution récursive :
1. Activité 2 :

Exécuter manuellement :
La fonction factoriel pour n = 4
F(4) = 4 * f (3)
F(3) = 3 * f (2)
F(2) = 2 * f (1)
F(1) = 1 * f (0)
F(0) = 0* f (-1)
Peut-on calculer le factoriel d’un nombre négatif ?

La fonction inverse pour ch = "salut"
Inverse ("salut") = "t" + Inverse("salu")
Inverse("salu") = "u" + Inverse("sal")
Inverse("sal") = "l"+ Inverse("sa")
Inverse ("sa") = "a" + Inverse("s")
Inverse ("s") = "s" + Inverse("")
Inverse ("") = "" + Inverse(?).
On doit s’arrêter
Page 1 sur 3

ALGO & PROG

PROF : Mohamed SAYARI

Interprétations :
Non bien sûr. Donc les appels récursifs doivent Lorsque la chaîne devient vide, on arrête les
être arrêté lorsque n = 0.
appels récursifs.
Lorsque n =0, factoriel(0) = 1
Lorsque ch =  , inverse ( ) =  
On appelle n = 0 le point d’arrêt de la fonction On appelle ch =   point d’arrêt de la fonction
factoriel
inverse

2 . C o n s ta ta tio n 2 :

Dans une définition récursive, on doit s’arrêter après autant d’appels récursifs.
Une solution récursive se traduit alors par une structure conditionnelle :
Si point(s) d’arrêt(s) alors
Valeur prise par la fonction si atteinte du point d’arrêt
Sinon
appel(s) récursif(s)
Fin si
Remarque :
Une solution récursive peut avoir 1 ou plusieurs points d’arrêts et encore 1 ou plusieurs appels récursifs.

Exemple 1 :
Calcul
factoriel d’un
nombre n

Fonction factoriel (n : entier) : entier long
Résultat =factoriel
Factoriel= [ ] Si n = 0 alors
Factoriel  1
Point d’arrêt
Sinon
Factoriel  n * factoriel (n-1)
Fin si

function factoriel(n: integer): longint;
begin
if n = 0 then
factoriel := 1
else
factoriel := n * factoriel(n - 1);
end;

Appel récursif

Exemple 2 :
Inversion
d’une chaîne
ch

Fonction inverse (ch : chaîne) : chaîne
Résultat = inverse
Inverse=[ ] si ch = "" alors
inverse  ""
sinon
inverse  ch [long(ch)] + inverse (sous-chaîne (ch,1,
long(ch)-1))
fin si

function inverse(ch: string): string;
begin
if ch = ‘’ then
inverse := ‘’
else
inverse := ch [length(ch)] + inverse
(copy (ch,1, length(ch)-1))
end;

3. Application:

Ecrire une analyse, un algorithme d'une fonction permettant de calculer le PGCD (plus grand
commun diviseur) de deux entiers positifs non nuls a et b, en utilisant la méthode de la différence
Exemple:
PGCD (22 , 6 ) = PGCD ( 22-6, 6 ) = PGCD ( 16,6) car 22 > 6
= PGCD (16-6 ,6 ) = PGCD (10 , 6) car 16 > 6
= PGCD (10-6, 6) = PGCD (4, 6) car 10 > 6
= PGCD (4, 6-4) = PGCD (4, 2) car 4 < 6
= PGCD (4-2, 2) = PGCD (2, 2) car 4 > 2
=2

Page 2 sur 3

ALGO & PROG

PROF : Mohamed SAYARI

* Interprétation
On remarque que:
Si a > b alors PGCD (a, b) = PGCD (a-b, a)
Si b>a alors PGCD (a, b) = PGCD (a, b-a)
Si a=b alors PGCD (a, b)=a (*** condition d'arrêt ****)
Nous remarquons qu'on a appelé la même fonction PGCD pour calculer le PGCD de a et b.
 Il s'agit d'un traitement récursif
La fonction PGCD devient:
0)
Fonction PGCD (a, b : entier) : entier
1)
Si a=b alors PGCD  a
Sinon si a>b alors PGCD  PGCD (a-b, b)
Sinon PGCD  PGCD (a, b-a)
Finsi
2)
Fin PGCD

IV. Remarques :
1. Activité 3:

 Ecrire un programme pascal qui permet de chercher et d’afficher l’inverse d’une chaîne
de caractères. (Utiliser au moins un module défini selon un procédé récursif).
 Testez avec les chaînes suivantes et déterminer les résultats trouvés :
Chaîne à introduire

Valeur retournée par le programme

"Salut"

………………………….

"Bonjour"

………………………….

"azertyuiopqsdfghjk"

………………………….

 Le programme a généré une erreur d’exécution. Rendez-vous au help de pascal, et
consulter la signification de l’erreur.
L’erreur est due à un débordement de mémoire.

2 . C o n s ta ta tio n 3
La récursivité utilise toujours la pile du programme en cours. (La pile est la mémoire stockant
les données intermédiaires de sous-programmes). lorsque le nombre des appels devient
important, la pile déborde. (cas de la chaîne azertyuiopqsdfghjk  )

V.

Applications :
Série N°2
Page 3 sur 3


Aperçu du document rcursivit.pdf - page 1/3

Aperçu du document rcursivit.pdf - page 2/3

Aperçu du document rcursivit.pdf - page 3/3




Télécharger le fichier (PDF)




Sur le même sujet..





Ce fichier a été mis en ligne par un utilisateur du site. Identifiant unique du document: 00205480.
⚠️  Signaler un contenu illicite
Pour plus d'informations sur notre politique de lutte contre la diffusion illicite de contenus protégés par droit d'auteur, consultez notre page dédiée.