ALGO & PROG PROF : Mohamed SAYARI

Page 1 sur 3

CCCHHHAAAPPPIIITTTRRREEE 222 :::

LLLAAA RRREEECCCUUURRRSSSIIIVVVIIITTTEEE II.. IInnttrroodduuccttiioonn ::

11.. AAccttiivviittéé 11 ::

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.

IIII.. DDééffiinniittiioonn ::

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

IIIIII.. PPrriinncciippee eett PPrréésseennttaattiioonn dd’’uunnee ssoolluuttiioonn rrééccuurrssiivvee ::

11.. AAccttiivviittéé 22 :: Exécuter manuellement :

La fonction factoriel pour n = 4 La fonction inverse pour ch = "salut"

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 ?

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

ALGO & PROG PROF : Mohamed SAYARI

Page 2 sur 3

Interprétations :

Non bien sûr. Donc les appels récursifs doivent être arrêté lorsque n = 0. Lorsque n =0, factoriel(0) = 1 On appelle n = 0 le point d’arrêt de la fonction factoriel

Lorsque la chaîne devient vide, on arrête les appels récursifs.

Lorsque ch = , inverse ( ) =

On appelle ch = point d’arrêt de la fonction inverse

22.. CCoonnssttaattaattiioonn 22 :: 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

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;

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;

33.. AApppplliiccaattiioonn:: 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

Point d’arrêt

Appel récursif

ALGO & PROG PROF : Mohamed SAYARI

Page 3 sur 3

* 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

IIVV.. RReemmaarrqquueess ::

11.. AAccttiivviittéé 33:: 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.

22.. CCoonnssttaattaattiioonn 33

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 )

VV.. AApppplliiccaattiioonnss ::

Série N°2