Récursivité : Analyse recursive

Pour résoudre un problème de manière récursive, on réalise une anlyse recursive.

Etape 1, Recherche d'un cas trivial : celui qui peut être résolu sans appel récursif (le critère d’arrêt) ; 

Étape 2, Paramétrage du problème : déterminer les paramètres en particulier la taille qui doit décroître a chaque appel récursif (converger vers le cas trivial);

Étape 3, Décomposition du cas général : ramener la résolution du problème a la résolution d'un ou de plusieurs problèmes de même nature et de taille plus petite (la partie récursive);

 

Exemple : Tour de Hanoї [Lucas 1883]:

Problème : 64 disques étant posés les uns sur les autres par ordre de taille décroissant sur un socle A, les transférer sur un socle B en utilisant un socle C en ne prenant qu'un disque a la fois pour le déposer sur un disque plus grand.

Réponse :

1. Analyse recursive

Étape 1 : avoir un seul disque (i.e. n=1) est un cas trivial car il suffit de le déplacer directement depuis le socle de départ vers le socle d’arrivée. D’où le critère d’arrêt :

si n=1 alors déplacer un disque du socle A vers le socle B

Étape 2 : n est le nombre de disques, socle de départ, socle d’arrivée et socle intermédiaire sont les paramètres. D’où : Action Hanoi(E/ n : entier ; E/ depart,arrivee,intermed : socle ) ;

Étapes 3 : Un socle contenant un disque plus grand que tous les autres est assimilable pour le transfert de ceux ci a une position vide. D’où la décomposition :

n disques peuvent être transférés de A vers B en :

• transférant n-1 disques de A vers C en utilisant B comme intermédiaire;
• déplacer le disque restant de A vers B ;
• transférant les n-1 disques de C vers B en utilisant A comme intermédiaire.

2. Algorithme

Action deplacer (E/x,y:caractere);

debut 

       ecrire('Deplacer un disque du socle',x,'vers le socle',y);

fin ;

Action Hanoi(E/ n:entier ; E/ x,y,z : caractere) ;

debut

    si n=1 alors

        deplacer(x,y) ;

    sinon

        Hanoi(n-1,x,z,y) ;

        deplacer(x,y) ;

        Hanoi(n-1,z,y,x) ;

    fsi ;

fin ;

Algorithme TourHanoi ;

debut

    Hanoi(64,'A','B','C') ;

fin.

3. En résumé [fom Wikipedia]:

« The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions. »  Niklaus Wirth, Algorithms + Data Structures = Programs.

«  La puissance de la récursivité réside évidemment dans la possibilité de définir des ensembles infinis d'objets par une affirmation finie. De façon similaire, un nombre infini d'étapes de calcul peut être décrit par un programme récursif fini, même si ce programme ne contient aucune répétition explicite. »

Bibliography and/or further reading:

1. Meyer B. et Baudoin C., Méthodes de programmation. Eyrolles 1984.

2. http://en.wikipedia.org/wiki/Tower_of_Hanoi

3. http://www.fil.univ-lille1.fr/~sedoglav/C/main019.html

Récursivité : Principe général

1. Squelette d'une action paramétrée récursive

 2. Mécanisme

Une vidéo décrivant le principe réalisée par un étudiant (que je remercie vivement) :

Construction d'une unité centrale simple

L'organisation matérielle des ordinateurs usuels suit l'architecture dite de Von Neumann (de Zuse ? Non pas de politique). Dans celle-ci :

• La RAM sert a stocker les données et les programmes ;
• Une unité de commande donne les ordres et synchronise l’exécution des opérations dans l’unité de traitement du processeur central.

Exemple :

Bibliography and/or further reading

1. Introduction a l'informatique. Tellier I. (http ://www.grappa.univ-lille3.fr/∼tellier/enseignement.html)

2. https://fr.wikipedia.org/wiki/Architecture_Harvard

3. http://fr.wikipedia.org/wiki/Discussion:Konrad_Zuse

4. http://en.wikipedia.org/wiki/Konrad_Zuse

TP10, codes sources

Prg1:
#include <stdio.h>
#include <stdlib.h>

int multIter(int x,int y)
{
   int prod=0;
   for(;y>0;y--)prod+=x;
   return prod;
}
int multRec(int x,int y)
{
   if(y==0) return 0;       //critere d'arret
   return x+multRec(x,y-1); //sinon recursion
}
int main()
{
    int a=11,b=3; //par exemple
    char tmp;
    printf("\nCode Iteratif: %d x %d = %d",a,b,multIter(a,b));
    printf("\nTapez Entree SVP");scanf("%c",&tmp);
    printf("\nCode Recursif: %d x %d = %d\n",a,b,multRec(a,b));
    return 0;
}

Prg2:
#include <stdio.h>
#include <stdlib.h>
unsigned int nbrDisq;
void Hanoi(unsigned n, char x, char y,char z,unsigned matSocles[][3]),
     deplacer (char x,char y, unsigned matSocles[][3]),
     initMatSocles(unsigned matSocles[][3],unsigned nbrDisq),
     modifMatSocles(char x,char y,unsigned matSocles[][3],unsigned nbrDisq),
     affichMat(unsigned mat[][3],unsigned,unsigned);
int main()
{
    printf("NbrDisques :");
    scanf("%u",&nbrDisq);
    unsigned matSocles[nbrDisq][3];
    initMatSocles(matSocles,nbrDisq);
    Hanoi(nbrDisq,'A','B','C',matSocles);
    return 0;
}

void deplacer (char x, char y, unsigned matSocles[][3])
{
    static unsigned mouvNbr=1;
    printf("\n Mouvement %u : Deplacer un disque du socle %c vers le socle %c \n",mouvNbr++,x,y);
    modifMatSocles(x,y,matSocles,nbrDisq);
    affichMat(matSocles,nbrDisq,3);
}
void Hanoi(unsigned n,char x,char y,char z,unsigned matSocles[][3])
{
    if (n>0){
        Hanoi(n-1,x,z,y,matSocles);
        deplacer(x,y,matSocles);
        Hanoi(n-1,z,y,x,matSocles);
    }
}
void initMatSocles(unsigned matSocles[][3],unsigned nbrDisq)
{
   unsigned i;
   for(i=0;i<nbrDisq;i++)matSocles[i][0]=i+1;
   for(i=0;i<nbrDisq;i++){matSocles[i][1]=0;matSocles[i][2]=0;}
   affichMat(matSocles,nbrDisq,3);
}

void modifMatSocles(char x,char y,unsigned matSocles[][3],unsigned nbrDisq)
{
   unsigned i1,i2;


   for(i1=0;(i1<nbrDisq)&&(matSocles[i1][x-65]==0);i1++){} //recherche du sommet du socle de depart

   for(i2=0;(i2<nbrDisq)&&(matSocles[i2][y-65]==0);i2++){} //recherche du sommet d'arrivee


   //transfert du disque
   matSocles[i2-1][y-65]=matSocles[i1][x-65];//ajout dans l'arrivee
   matSocles[i1][x-65]=0;//suppression dans le depart
}
 void affichMat(unsigned mat[][3],unsigned n,unsigned m)
 {
    unsigned i,j;
    for(i=0;i<n;i++){
        for(j=0;j<m;j++)printf("%4d",mat[i][j]);
        printf("\n");
    }
 }

Resumé du Chapitre 4, Actions Paramétrées

Syntaxe de défintion/déclaration

A la place de Action, on peut mettre Procedure.

Exemples de procedures :

1.

Action Additionner (E / X,Y : Entier ; S / Som : Entier) ;

Début

Som ← X + Y ;

Fin ;

Algorithme Addition ;{algorithme principal}

Var

A,B,somme : Entier ;

Début

Lire(A,B) ;

Additionner(A,B,somme) ;{appel de l’action paramétrée Addition}

Ecrire(somme) ;

Fin.

2.

Action Addit (E / N : Entier ; S / Som : Entier) ;

Var

I : Entier ;

Début

Som ← 0 ;

Pour i ← 1 à N Faire

Som ← Som + i ;

Fait ;

Fin ;

Algorithme Addition ;{algorithme principal}

Var

N,somme : Entier ;

Début

Lire(n) ;

Addit(n,somme) ;{appel de l’action paramétrée Addit}

Ecrire(somme) ;

Fin.

Exemples de fonctions :

1. Somme de deux nombres :

Fonction Somme(E/ a,b : Entier) : Entier ;

Début

    retourner a+b ;

Fin ;

Algorithme sommation ;{algorithme principal}

Var

A,B,Som : Entier ;

Début

    Lire(A,B) ;

    Som ← Somme(A,B) ;

    Ecrire(Som) ;

Fin.

2. Algorithme déterminant la valeur de la formule 2Min(A,B)+1 :

Fonction Minimum(E/ a,b : Entier) : Entier ;

Var Min : Entier ;

Début

    Si a<b Alors Min ← a ;

    Sinon Min ← b ;

    Fsi ;

    retourner Min ;

Fin ;

Algorithme Formule ;

Var A,B,form : Entier ;

Début

    Lire(A,B) ;

    form ← 2Min(A,B)+1 ;

    Ecrire(form) ;

Fin.

Modes de transmission

3+1 modes : E, S, ES et REF.

Visibilité

Exemple :

Action suivant(ES/ z:entier) ;

debut z ← z+1 ; fin ;

Action addit(E/x,y:entier ; S/som :entier) ;

var val:entier ;

debut

   som ← x ;

   val ← 0 ;

   Tant que val<y faire

     suivant(som) ;

     suivant(val) ;

   ftq ;

fin ;

Algorithme Additionner ;

var A,B,somme:entier ;

debut

    lire(A,B) ; 

    addit(A,B,somme);

    ecrire(somme) ;

fin.

Objets déclarés dans	Portée
A : Additionner	A, SA1, SA2
SA1 : Addit	SA1, SA2
SA2 : suivant	SA2

TP 9, codes sources

Programme 1:
#include <stdio.h>
#include <stdlib.h>
void afficheTab(int[],int);
int vect[10],taille;
int main()
{
    afficheTab(vect,taille);
    return 0;
}
void afficheTab(int vect[],int taille){
    int i;
    printf("\n les elements de votre tableau sont:\n");
    for(i=0;i<taille;i++){
       printf("\t%d",vect[i]);
    }
}

Programme 2:
#include <stdio.h>
#include <stdlib.h>
void remplirMat(int [][10],int*,int*),
     affichMat(int [][10],int,int);
int mat[10][10],N,M;
int main(){
    remplirMat(mat,&N,&M);
    affichMat(mat,N,M);
    return 0;
}
void remplirMat(int tab[][10],int*N,int*M){
int i,j;
printf("\nDonner le nombre de lignes <=10: ");
scanf("%d",N);
printf("\nDonner le nombre de colonnes <=10: ");
scanf("%d",M);
for(i=0;i<*N;i++){
     for(j=0;j<*M;j++){
        printf("\ndonner l'element %d,%d :",i+1,j+1);
        scanf("%d",&tab[i][j]);
     }
 }
}
void affichMat(int tab[][10],int N,int M){
   int i,j;
   for(i=0;i<N;i++){
     for(j=0;j<M;j++){
        printf("%5d",tab[i][j]);
     }
     printf("\n");
   }
}

Les autres prgs je ne les ai pas. Il faut les réécrire.

TP 8, codes sources

Programme 1:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    int fin,debut=0,droite,gauche;
    char mot[100],tmp;
    printf(" donner un mot \n");
    scanf("%s",mot);
    fin=strlen(mot)-1;

    for(droite=fin,gauche=debut;gauche<droite;gauche++,droite--){
       tmp=mot[droite];
       mot[droite]=mot[gauche];
       mot[gauche]=tmp;
    }

    printf(" le mot miroir est %s \n",mot);
    return 0;
}

L'execution de ce programme donne :

Programme 2: A deboguer

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int fin,debut,gauche;
char mot[100];
int main()
{
    char tmp;
    printf(" Donner un mot ");
    scanf("%s",mot);
    debut=0;
    fin=strlen(mot);

    for(gauche=debut;gauche<fin/2;gauche++){
        tmp=mot[fin-gauche];
        mot[fin-gauche]=mot[gauche];
        mot[gauche]=tmp;
    }

    printf(" le mot miroir est %s \n",mot);
    return 0;
}