Informatique-solution de l'algorithm récursif : series d’exercice N01

Informatique-solution series d’exercice N01 de algorithm récursif :

Ex 01 :

Fonction Somme(n :entier) :entier

Début

Si  n=0  alors

Somme <== 0

sinon

Somme  <==Somme(n+1)+n

Fin

Ex 02 :

a)Fonction quotion(a,b :entier) :entier

Début

Si b<>0 alors

      Début

      Si a<b alors

           quotion<== 0

      Sinon

      quotion   <==quotion(a-b,b)+1

     fin

sinon

quotion   <==  -1

Fin

 b) Fonction reste(a,b :entier) :entier

      Début

      Si a<b alors

          reste <==  a

      Sinon

                                                                 Reste   <==       reste (a-b,b)+1

     Fin

Ex 03 :

Procédure   parcours (tete :pointeur)

  Variable p :pointeur

                  i :entier

 Début

    p   <==  tete

    i   <== 0

   Si p< > NIL alors

   Début

    …….(traiter(p))

    Parcours(suivant(p))

   Fin

Fin

Ex 04 :

Fonction   longer (tete :pointeur) :entier

  Variable p :pointeur

 Début

    p   <== tete  

   Si p= NIL alors

   Longer <== 0

Sinon

    Longer <==Longer(suivant(p)+1)

   Fin

Ex 05 :

Fonction   count (tête :pointeur, val=entier) :entier

  Variable p :pointeur

 Début

    p   <== tête  

   Si p= NIL alors

   Count<== 0

Sinon

      count<== count(suivant(p)+1)

       sinon

      count<== count(suivant(p))

 Fin

Ex 06 :

a)Fonction   Rech (tête :pointeur, val=entier) :entier

  Variable p :pointeur

                   a:entier

 Début

    p<==tet  

   Si p= NIL alors

      Rech<==  NIL

Sinon

       Si a=val   alors

      Rech <==p

Sinon

                  Rech<== Rech(suivant(p),val)

Fin

b)

Fonction   position (tête : pointeur, pos=entier) : pointeur

  Variable p :pointeur

 Début

    p<== tête  

   Si  pos> 0    alors

     début

      Si pos=1   alors

      position <== p

       Sinon

       Si p=NIL   alors

       position <== NIL

       Sinon

      position<==  position(suivant(p),pos-1)

      fin

Fin

Ex 07 :

Fonction   s-liste (tete-l,tete-sl :pointeur) :booléen

  Variable p,q :pointeur 

 Début

    p <== tète -l 

    q<== tète -sl 

   Si p= NIL     alors

        s-liste <==faux

       Si corespond(p,q)    alors

      s-liste <==  vrai

Sinon

      s-liste<== s-liste(suivant(p),q)

fin

Ex 08 :

Fonction somme(a,b :entier) :entier

Début

Si   a< b   alors

   Début

c<== a

a<== b

b<== c

fin

si b=0   alors

somme<== a

sinon

somme<== somme(a+1,b-1)

Fin

Ex 09 :

a)Fonction prod(t :tableau de entier,n :entier) :entier

    variable  i :entier

Début

Si  n=1  alors

prod<== t[i]

sinon

   prod <==prod(t,n-1)*t[n]

Fin

b)Fonction moyenne(t :tableau[] :entier,n :entier) :entier

Début

Si  n=1  alors

moyenne <==t[1]

sinon

 moyenne <==((n-1)*moyenne (t,n-1)+t[n]) /n

Fin

Quand utiliser la récursivité ?

*Quand la décomposition est simple à trouver et à comprendre .

Quand ne pas utiliser la récursivité ?

*Quand il existe une solution itérative simple et intuitive.

*Quand la problème de la récursivité est trop grand (dépassement possible de la pile d’exécution).