Cours et exercices de mathématiques M. CUAZ, [Link]
fr
TURBO PASCAL
RECURSIVITE
1) Un premier exemple
Le but est d'écrire un programme en langage Turbo-Pascal permettant de calculer les termes d'une suite de
Fibonacci quelconque, c'est à dire de la forme :
un + 2 = au n +1 + bu n
a, b, u 0 et u1 quelconques
1-1) Une première solution
Une première solution peut consister à écrire un programme qui, une fois les quatre éléments "de base"
a, b, u 0 , u1 donnés, va calculer les termes de la suite (u n )n∈IN de manière "ascendante", c'est à dire
u 0 , u1 , u 2 , etc... jusqu'à un arrêt provoqué par un test sur l'indice ou par l'utilisateur, à qui on aurait demandé au
préalable l'indice qu'il souhaitait obtenir.
Exercice :
Ecrire un programme dont un algorithme serait :
- Entrée par l'utilisateur des valeurs a, b, u 0 , u1
- Entrée par l'utilisateur de l'indice N correspondant au terme u N souhaité
- Série de calcul des u i (pour i variant de 2 à N) et affichage du terme u N lorsque celui-ci est calculé
Page 1/6
Cours et exercices de mathématiques M. CUAZ, [Link]
Proposition de Programme Commentaires
Program FiboGen1; Rappel : les accolades {} peuvent servir à commenter votre programme et ne
{programmation de U0,U1,a,b,n avec nuisent pas à son exécution. Ne pas hésiter à en employer donc.
Un+2=a*Un+1+b*Un }
var a,b,x,y,z:real; i,n:integer;
begin
write(‘entrez a,b,u0,u1,n’) ;
readln(a,b,x,y,n) ;
for i:=2 to n do begin Les jeux d'affectation entre les trois variables x,y, et z (respectivement
z:=a*x+b*y u n , u n +1 et u n + 2 ) sont les suivants :
x:=y
y:=z Au niveau n, x = u n , y = u n +1 , donc :
end;
u n + 2 = au n + bu n +1 ⇔ z = ax + by
writeln('U',n,'=',z); Au niveau n+1, l'égalité u n + 3 = au n +1 + bu n + 2 nécessite de transférer
END.
u n + 2 à la place de u n +1 , c'est à dire z à la place de y, et u n +1 à la place de
u n , c'est à dire y à la place de x.
Syntaxe : La fin du programme est symbolisée par le point après le mot END
Variantes pour la boucle :
for i:=2 to n do begin
z:=a*x+b*y
x:=y
y:=z
end;
On peut aussi saisir :
i:=1
While i<n do begin
z:=a*x+b*y
x:=y
y:=z
i:=i+1
end;
ou encore
i:=1
Repeat
z:=a*x+b*y
x:=y
y:=z
i:=i+1
until i=n
Page 2/6
Cours et exercices de mathématiques M. CUAZ, [Link]
1-2) Une deuxième solution
Une deuxième solution peut consister à écrire un programme qui, une fois les quatre éléments "de base"
a, b, u 0 , u1 donnés, ainsi que l'indice N correspondant au terme u N souhaité par l'utilisateur, va calculer les
termes de la suite (u n )n∈IN de manière "descendante",
c'est à dire va commencer à vouloir calculer u N ,
dont le calcul nécessite celui de u N −1
dont le calcul nécessite celui de u N − 2
etc…
dont le calcul nécessite celui de u 2
dont le calcul nécessite celui de u1 et de u 0 , mais ces deux dernières valeurs sont acquises.
Nous allons donc construire une fonction chargée de calculer un terme u n ( n ≥ 2 ), grâce à la formule
u n = au n −1 + bu n − 2 ( n ≥ 2 ), laquelle fonction s'auto-appellera , jusqu'à ce que les rangs 1 et 0 soient atteints,
auxquels cas les résultats de la fonction devront être les valeurs u 0 ,u1 données au début, afin que la série
d'appels mutuels puisse prendre fin
Exercice :
Ecrire un programme dont un algorithme serait :
- Procédure demandant à l'utilisateur de saisir les valeurs a, b, u 0 , u1 et celle de l'indice N correspondant au
terme u N souhaité (cette procédure n'est utilisée qu'une fois en début de programme)
- Ecriture d'une fonction, de paramètre a, b, u 0 , u1 et n, chargée du calcul de u n telle que :
- Si n=0 ou n=1, la fonction retourne u 0 ou u1
- Sinon la fonction s'auto-appelle deux fois (puisque le calcul de u n nécessite celui de u n −1 et de u n − 2 )
- Initialisation de cette fonction avec comme paramètres a, b, u 0 , u1 et N.
Page 3/6
Cours et exercices de mathématiques M. CUAZ, [Link]
Proposition de Programme Commentaires
Rappel : les accolades {} peuvent servir à
Program FiboGen2; commenter votre programme et ne nuisent pas à
{programmation de U0,U1,a,b,n avec son exécution. Ne pas hésiter à en employer donc.
Un+2=a*Un+1+b*Un }
var a,b,u0,u1:real; n:integer;
Ne pas oublier de mentionner le type du résultat du
function suite(n:integer):real; calcul de la fonction. Ici real
begin Dans le corps de description de la fonction, seul
if n=0 then suite:=u0 ; son nom est utilisé en cas d'affectation (symbole
if n=1 then suite:=u1 ; ":=")
C'est la ligne fondamentale d'auto-appel de la
if n>1 then suite:=a*suite(n-1)+b*suite(n-2); fonction
end;
Début du programme
BEGIN
write(‘entrez a,b,u0,u1,n’) ;
readln(a,b,x,y,n) ;
writeln('Un=',Suite(n):8:4) ; Initialisation de la fonction avec le paramètre n
Syntaxe : La fin du programme est symbolisée par
END. le point après le mot END
Page 4/6
Cours et exercices de mathématiques M. CUAZ, [Link]
2) Autre exemple : Le triangle de Pascal
Rappel :
Les coefficients binomiaux sont les C np , où p et n sont deux entiers, avec :
Si p>n , C np = 0 .
Si n=0 ou p=0 ou n=p alors C np =1.
n!
Dans tous les autres cas, C np =
(n − p )! p!
La formule de Pascal (permettant de dresser le triangle du même nom) est :
C np + C np +1 = C np−+11 ,
que l'on peut lire "à l'envers" sous la forme :
C np = C np−−11 + C np−1
(toujours avec les conventions habituelles sur les indices)
Exercice :
- Construire une fonction récursive C , de paramètres p et n entiers, retournant 1 dans les cas pathologiques du
calcul de C np (voir ci-dessus) et utilisant sinon la formule de récursivité C np = C np−−11 + C np−1 .
- Construire un programme permettant de dresser le triangle de Pascal à l'aide de deux boucles emboîtées l'une
dans l'autre (respectivement n et p), pour n entier tel que 0 ≤ n ≤ 6 .
Page 5/6
Cours et exercices de mathématiques M. CUAZ
Proposition de Programme Commentaires
Rappel : les accolades {} peuvent servir à commenter votre programme et
Program TrPascal; ne nuisent pas à son exécution. Ne pas hésiter à en employer donc.
Var n,p:integer;
{Fonction récursive permettant de
tracer le triangle de Pascal }
Function C(n,p: integer):integer; Cas pathologiques
Begin
if (n=0) or (p=0) or (n=p) then C:=1
else C:=C(n-1,p-1)+C(n-1,p)
End; 2 boucles imbriquées l'une dans l'autre
Appel de la fonction
Begin
for n:=0 to 6 do begin Instruction pour retourner au début de la ligne suivante
for p:=0 to n do
write(C(n,p):5); Syntaxe : La fin du programme est symbolisée par le point après le mot
writeln; END.
end;
readln
end.
Page 6/6
