Révision de la récursivité: exercices corrigés et méthodes

EXERCICE N°1
Transformer la procédure suivante en une procédure récursive:
0/ Début Procédure Calcul (N : entier, var P : réel)
1/ P <-- 1
2/ Pour i de 1 à N faire
P <-- P * i
Fin Pour
3/ Fin Calcul
--------------------
calcul(5, p)
p=1
p=1
p=2
p=2x3
p=2x3x4
p=2x3x4x5

=> p = n!

Code:

Fonction récursive
Début Fonction Calcul(n:Entier)
    si (n<=1) alors
        Calcul <-- 1
    sinon
        Calcul <-- n * Calcul(n-1)
    finsi
Fin Calcul

Procédure récursive

Code:

Début Procédure Calcul(i:Entier,n:Entier, var p: Entier)
    Si (i<=n) Alors
        p <-- p * i;
        Calcul(i+1,n,p)
    FinSi
Fin Calcul

EXERCICE PREPARATION POUR 2°

Ecrire un programme récursif qui affiche tout le contenu d'un tableau T de taille n.

Ent itératif :

Code:

Pour i de 1 à n faire
  Ecrire(T[i])
FinPour

En récursif (version 1)

Code:

PROC Afficher (i: ENTIER; T:TAB; n:ENTIER)

    SI (i <= n) ALORS
        ECRIRE(T[i])
        Afficher(i+1, T, n)
    FINSI

FINPROC

En récursif (version 2)

Code:

PROC Afficher (T:TAB; n:ENTIER)

    SI (n>=1) ALORS
        Ecrire (T[n])
        Afficher(T, n-1)
    FINSI

FINPROC

EXERCICE N°2

Transformer en sous-programme récursif :

Code:

0/ PROCEDURE F( T: TAB, N: ENTIER, VAR m )

1/ m <-- 1

2/ POUR i de 2 à n FAIRE

      SI (T[m] < T[i] ) ALORS
          m <-- i
      FINSI

  FINPOUR 

3/ F <-- m
   
4/ FIN FONCTION

Exemple: T=[2,1,5], n=3
m=1
i=2 : ?
i=3 : T[1] < T[3] <=> 2 < 5? oui, m=3.
F = 3: elle retourne le rang du maximum du tableau T.

Solution :

Cette procédure récursive fait le parcours d'un tableau T de taille n.

m: rang du maximum

i:=2 (position de début de la recherche)
m:=1 (initialisation externe, avant l'appel de la proc récursive)

Code:

PROC Recherche (i: ENTIER; T:TAB; n:ENTIER; var m: ENTIER)
Début
    SI (i <= n) ALORS
        SI (T[m]<T[i]) ALORS
            m <-- i
        FINSI
        Recherche (i+1, T, n, m)
    FINSI
FINPROC

Appel de la procédure récursive Recherche

Exemple: T = [2,1,9,5], n=4, m=1

m<--1
i<--2
Recherche (i, T, n, m)

EXERCICE N°3

Transformer en sous-programme récursif :

Module de de calcul de l'occurence (nombre d'apparitions) d’un entier X dans un tableau T de taille n.

Version itérative

Code:

Début Occurence (T:TAB, n:ENTIER, X:ENTIER): ENTIER
    p <-- 0
    Pour i de 1 à n Faire
        Si (T[i] = X) ALORS
            p <-- p + 1
        FINSI
    FinPour
    Occurence <-- p
Fin Existe

Version Procédure Récursive n°1
=================

Code:

Début Proc Occurence (i: ENTIER, T:TAB, n:ENTIER, X:ENTIER, VAR p: ENTIER)
    Si ( i <= n) ALORS
        Si (T[i] = X) Alors   
            p <-- p + 1
        FinSi
        Occurence(i+1, T, n, X, p)
    FINSI
Fin Occurence

Appel de la procédure récursive
a) initialisation de p (p <-- 0) et i à 1
b) Occurence(i, T, n, X, p)

Version Fonction Récursive n°2
=================

Code:

Début Fonction Occurence (i: ENTIER, T:TAB, n:ENTIER, X:ENTIER):Entier
    Si (i<=n) Alors
        Si (T[i]=X) Alors
            Occurence <-- 1 + Occurence(i+1,T,n,X)
        Sinon
            Occurence <-- Occurence(i+1,T,n,X)
        FinSi
    FinSI
Fin Occurence

EXERCICE N°4

Transformer en sous-programme itératif :

Module récursif qui calcule la somme des chiffres d'un nombre entier positif.
Version Procédure Récursive n°1
Version Fonction Récursive n°2

Exemple: N=1245

5 => Comment je trouve 5?
1ère méthode:
N mod 10
2ème méthode:
a) convertit N en chaine de caractères CH
b) Je calcule la longueure de la chaine L
c) '5' = CH[L]
d) je reconvertis le caractère '5' en entier

4 =>
1ère méthode
(N div 10) mod 10

2 =>
1ère méthode
(N div 100) mod 10

1 => etc...


EXERCICE N°5

Transformer en sous-programme récursif :

Module de recherche d’un entier X d’un tableau T de taille n.

Version Procédure Récursive n°1
Version Fonction Récursive n°2

Code:

program recherche_dico_ite;
uses wincrt;

type
    TAB = array[1..100] of integer;


Var
  T: TAB;
  N,X: integer;


procedure saisie(var n:integer; var T:TAB; var X:integer);
var
 i: integer;
begin

    repeat
          write('n=');
          readln(n);
    until (n in [1..100]);

    for i:=1 to n do
    begin
          write('T[',i,'] = ');
          readln(T[i]);
    end;

    write('X = ');
    readln(X);

end;


{ le tableau doit être trié dans l'ordre croissant}
function dicho_itera(T:TAB; n:integer;x: integer):boolean;
var
  G,D,Milieu:integer;
  Trouve:Boolean;
begin
    G := T[1];
    D := T[n];
    Trouve := false;

    if ((x < T[1]) or (x>T[n])) then
        dicho_itera := false
    else
        if ((x=T[1]) or (x=T[n])) then
          dicho_itera := true
        else
          repeat
              Milieu := (G+D) div 2;
              if (T[milieu] = x) then
              begin
                  Trouve := true;
              end
              else
                  if (x < T[milieu]) then
                    D := milieu
                  else
                    G := milieu;
          until ((trouve=true));               
end;


function dicho_rec(G,D: integer; T:TAB; n:integer;x: integer):boolean;
var
  Milieu: integer;
begin

    if (G>D) then
        dicho_rec := false
    else
    begin
        Milieu := (G+D) div 2;
        if (T[Milieu] = x) then
          dicho_rec := true
        else
            if (x<T[Milieu]) then
              dicho_rec := dicho_rec(G,Milieu-1,T,n,x)
            else
              dicho_rec := dicho_rec(Milieu+1,D,T,n,x);
    end;
end;

Begin
repeat
  saisie(N,T,X);
  writeln('Résultat = ',dicho_rec(1,N,T,N,X));
until (1=0);
End.