programmation

-I- Introduction :
La récursivité est une concept l'on se trouve
fréquemment dans la vie quotidienne:des histoires à l'intérieur
d'histoire, des tableaux dans des tableaux, des poupées gigognes.
En terme informatique, un objet est dit récursif, s'il se contient lui-même ou s'il est définit à partir de lui-même.
Pascal permet qu'une procédure ou une fonction s'appelle elle lui-même, une telle procédure ou fonction est appelée récursive.
Exemple :
On
définit une suite de nombre tels que le niéme élément de cette suite
soit égale à la somme de deux précédents. On décide que les deux
premiers nombres sont 0 et 1. la suite obtenue est la suivante: 0 1 1 2
3 5 8 13 21 34 55…
Formellement, si le niéme nombre est noté fn. Tout élément se calcul par la formule:
Fn = fn-1 + fn-2.
Une
telle formule est dite récursive car le calcul implique la connaissance
de fn-1 et fn-2 qui eux même impliquant celles de fn-3 et fn-4 etc…
Notons que les fi sont appelés nombres de fibancci. Dans ce cas une fonction fournissant le nombre cherché s'impose.
Analyse:
Pour écrire le corps de cette fonction. Il faut considérer trois cas:
pour n = 0 la fonction donne 0 comme résultat.
pour n = 1 la fonction donne 1 comme résultat.
pour n la fonction donne fn-1 + fn-2 comme résultat
On obtient donc la fonction suivante:

Function fib (n: integer): integer;
Begin
If n = 0 then
F := 0
Else if n = 1 then
F := 1
Else
F := fib (n-1) + fib (n-2);
Fib := F ;
End;




-II- définition et principes:
Un
sous programme est dit récursif lorsqu'il s'appelle lui-même dans sa
définition (récursivité directe), et éventuellement s'il s'appelle par
l'intermédiaire d'autres sous programmes appelés par lui-même
(récursivité indirecte).
Si un sous programme S1 appelle un sous programme S2 qui appelle S1, on parle de récursivité croisée.
Chaque langage de programmation permettant l'emploi de la récursivité,
utilise au niveau de la mémoire centrale une pile des états actifs, ou
la dernière information entrée est aussi la première à sortir. On parle
d'une liste LIFO (Last In First Out).
Si le nombre d'appels
récursifs est important, il peut y avoir un dépassement de la capacité
de mémoire provoquant ainsi un arrêt de l'exécution du programme.
Tout algorithme récursif doit distinguer plusieurs cas, dont l'un au
moins ne doit pas comporter d'appel récursif, sinon risque de cercles
vicieux et de calcul infini. Les cas non récursifs d'un algorithme
récursif sont appelés cas de base ou conditions de terminaison.
-III- applications:
Application 1:
On se propose d'écrire un sous programme récursif permettant de calculer le factorielle d'un entier naturel N > 0.
Application 2:
On se propose d'écrire un sous programme récursif permettant de calculer xy avec x un réel donné et y un entier donné.
Application 3:
On se propose d'écrire un sous programme récursif permettant de
calculer le plus grand commun diviseur de deux entiers positifs A et B
donnés.
Application 4:
On se propose d'écrire un sous programme récursif permettant de vérifier si un entier N > 0 est premier ou non.
Application 5:
On se propose d'écrire un sous programme récursif permettant de vérifier si une chaîne donnée est palindrome ou non.
Application 6:
On se propose d'écrire un sous programme récursif permettant de
vérifier l'existence d'un entier E donné dans un tableau T de n entiers
triés dans l'ordre croissant, en utilisant la technique de recherche
dichotomique.
Application 7:
On se propose d'écrire un sous
programme récursif permettant de trier un tableau T de n entiers en
utilisant le principe de tri par sélection.
-IV- Solution:
Application 1:
Def FN fact (n:entier) entier
Résultat : fact ç f
Traitement :
f =[] si n = 1 alors
Fç 1
Sinon
Fç n*fact (n-1)
Fin si

Application 2:
Def FN puissance (x :reel ;y,c :entier) :reel
Résultat : puissance çp
Traitement:
P=[] si c< abs(y) alors
[] si y<0 alors
pç 1/puissance(x,-y,c)
sinon
pç puissance (x,y,c+1)
fin si
sinon
pç 1
fin si

Application 3:
Def FN PGCD (A,B : entier):booleen
Résultat: PGCDç R
Traitement:
R= [] si B=0 alors
Rç A
Sinon
Rç PGCD(B,A MOD B)
Fin si




Application 4:
Def FN premier (N,D:entier):booleen
Résultat: premierçV
Traitement:
V=[] si D>SQRT(N) alors
Vç vrai
Sinon
Si (N MOD D = 0) alors
Vç faux
Sinon
Vç premier(N,D+1)
Fin si
Fin si
Application 5:
Def FN pal(ch :chaîne) :booleen
Résultat: palç p
Traitement:
P= [] si ch= "" alors
Pç vrai
Sinon si ch[1]<> ch[long(ch)] alors
Pç faux
Sinon
Pç pal(sous chaîne(ch,2 ,long(ch)-2))
Fin si

Application 7:
Def PROC tri_sel(var t:tab;n,i:entier)
Résultat: t
Traitement:
T= [] si i <= n-1 alors
Pmç FN posmin(t,i,n)
[] si pm<> i alors
auxç t[i]
t[i]ç t[pm]
t[pm]ç aux
fin si
tri_sel(t,n,i+1)
fin si




Def FN posmin(t:tab;d,f:entier):entier;
Résultat: posminç p
Traitement:
P= [pç d] pour i de d+1 à f faire
Si t[i]
Pç i
Fin si
Fin pour

merci baaaaaaaaaaaaaarcha