INF1101 Algorithmes et structures de données1 Cours 5 La récursivité

INF1101 Algorithmes et structures de données

1

Cours 5Cours 5

La récursivitéLa récursivité


2

Plan du coursPlan du cours

I.I. Notions de base Notions de baseII.II. Exemple simple (imp. de nombres)Exemple simple (imp. de nombres)III.III. Limitations (suite de Fibonacci) Limitations (suite de Fibonacci)IV.IV. Arbres (introduction) Arbres (introduction) V.V. Autres exemplesAutres exemplesVI. Sous-séquence de somme maximaleVI. Sous-séquence de somme maximaleVII. BacktrackingVII. Backtracking


3

I - Notions de baseI - Notions de baseDéfinition:Définition:

Un objet est récursif s'il est défini à partir de lui-même. Une Un objet est récursif s'il est défini à partir de lui-même. Une fonction est récursive si elle fonction est récursive si elle peutpeut s'appeler elle-même de s'appeler elle-même de façon directe ou indirectefaçon directe ou indirecte

Idée générale:Idée générale: Pour bien comprendre la notion de récursivité, il faut Pour bien comprendre la notion de récursivité, il faut

connaître le concept des piles.connaître le concept des piles.

Les piles sont des structures qui peuvent contenir plusieurs Les piles sont des structures qui peuvent contenir plusieurs éléments. Toutefois, seul le dernier élément ajouté à la pile éléments. Toutefois, seul le dernier élément ajouté à la pile est accessible.est accessible.

Une analogie peut être faite avec les piles d'assiettes. Seule Une analogie peut être faite avec les piles d'assiettes. Seule l'assiette du dessus est immédiatement accessible. De la l'assiette du dessus est immédiatement accessible. De la même façon, lorsqu'une assiette est ajoutée, celle-ci est même façon, lorsqu'une assiette est ajoutée, celle-ci est nécessairement déposée sur le dessus de la pile.nécessairement déposée sur le dessus de la pile.


4

La pile d’assietteLa pile d’assiette

Assiette disponibleAssiette disponible

Lorsqu'une fonction est appelée, ses paramètres formels, l'adresse de Lorsqu'une fonction est appelée, ses paramètres formels, l'adresse de retour et les variables locales (automatiques) de la fonction appelée sont retour et les variables locales (automatiques) de la fonction appelée sont déposés sur la pile. Toutes ces données sont retirées de la pile à la findéposés sur la pile. Toutes ces données sont retirées de la pile à la finde l'exécution de la fonction. Conséquemment, lors d'appels récursifs, de l'exécution de la fonction. Conséquemment, lors d'appels récursifs, les variables de la fonction sont empilées en cascade.les variables de la fonction sont empilées en cascade.


5

Récursivité (suite)Récursivité (suite)

Idée généraleIdée générale : :La réalisation d'une tâche par un algorithme La réalisation d'une tâche par un algorithme

récursifrécursifrepose sur deux éléments:repose sur deux éléments:

• La résolution partielle du problème d'une façon La résolution partielle du problème d'une façon simple. La réalisation du reste de la tâche étant simple. La réalisation du reste de la tâche étant déléguée aux appels récursifs successifs.déléguée aux appels récursifs successifs.

• La détermination d'une condition d'arrêt qui La détermination d'une condition d'arrêt qui permet d'arrêter la cascade d'appels récursifs. permet d'arrêter la cascade d'appels récursifs. Résoudre le problème au moment où la condition Résoudre le problème au moment où la condition d'arrêt est détectée correspond en général à d'arrêt est détectée correspond en général à résoudre un cas trivial de celui-ci.résoudre un cas trivial de celui-ci.


6

Champs d'application des Champs d'application des algorithmes récursifsalgorithmes récursifs

• Structures de données définies Structures de données définies récursivement (listes, arbres, graphes, récursivement (listes, arbres, graphes, etc.)etc.)

• Équations de récurrence (algébriques, Équations de récurrence (algébriques, vectorielles, booléennes, formelles, vectorielles, booléennes, formelles, ensemblistes, etc.);ensemblistes, etc.);

• Rétroaction ("backtracking").Rétroaction ("backtracking").• ……


7

Avantages et inconvénientsAvantages et inconvénients

Avantages:Avantages:• Formulation compacte, claire et élégante.Formulation compacte, claire et élégante.• Maîtrise des problèmes dont la nature même Maîtrise des problèmes dont la nature même

est récursive.est récursive.

Désavantages:Désavantages:• Possibilité de grande occupation de la Possibilité de grande occupation de la

mémoire.mémoire.• Temps d'exécution peut être plus long.Temps d'exécution peut être plus long.• Estimation difficile de la profondeur Estimation difficile de la profondeur

maximale de la récursivité.maximale de la récursivité.


8

Fonction récursive Fonction récursive factoriellefactorielle

long Factorielle(long N){ if (N==0) return 1; else return (Factorielle(N-1)*N);}Voir main1.cpp

Soit la fonction Factorielle, effectuant l’opération Soit la fonction Factorielle, effectuant l’opération n!n!


9

Exécution de FactorielleExécution de Factorielle

Factorielle (4)Factorielle (4)

int Reponse = Factorielle (4);int Reponse = Factorielle (4);

Factorielle (3)Factorielle (3) Factorielle (2)Factorielle (2) Factorielle (1)Factorielle (1) Factorielle (0)Factorielle (0)


10

Récursivité (suite)Récursivité (suite)

Quatre règles régissent la récursivitéQuatre règles régissent la récursivité::1.1. Présence de cas de base pouvant être Présence de cas de base pouvant être

résolu sans récursivitérésolu sans récursivité2.2. Toujours progresser vers le cas de base à Toujours progresser vers le cas de base à

chaque appel récursifchaque appel récursif3.3. « Ayez la Foi »: avoir confiance que les « Ayez la Foi »: avoir confiance que les

appels récursifs progressent réellement appels récursifs progressent réellement vers le cas de base.vers le cas de base.

4.4. Intérêt composé: Ne jamais dédoubler du Intérêt composé: Ne jamais dédoubler du travail dans deux appels récursifs travail dans deux appels récursifs différents.différents.


11

II – Exemple simple : II – Exemple simple : impression de nombresimpression de nombres

Idée générale:Idée générale: Fonction qui donne l’impression d’un nombre Fonction qui donne l’impression d’un nombre

non-négatif N sous forme décimale. Par non-négatif N sous forme décimale. Par exemple pour le nombre 248, il est exemple pour le nombre 248, il est nécessaire d’imprimer 2, puis 4 et finalement nécessaire d’imprimer 2, puis 4 et finalement 8. La récursivité offre une méthode efficace 8. La récursivité offre une méthode efficace et simple de programmer une tel méthode.et simple de programmer une tel méthode.

En utilisant l’opérateur %, le dernier chiffre En utilisant l’opérateur %, le dernier chiffre peut être imprimer, suivi des autres par npeut être imprimer, suivi des autres par n/10./10.


12

Fonction récursive pour N Fonction récursive pour N en forme décimaleen forme décimale

void printDecimal( int n )

{

if ( n >= 10 )

printDecimal( n/10 );

cout.put( ‘0’ + n%10 );

}


13

Fonction récursive pour N Fonction récursive pour N pour n’importe quelle basepour n’importe quelle base

void printInt( int n , int base){ static string DIGIT_TABLE = “0123456789abcdef”;if ( n >= base )

printInt( n/base, base ); cout << DIGIT_TABLE[ n%base ];}


14

Exemple simple : impression Exemple simple : impression de nombresde nombres

Note :Note : Une erreur se produit lors de l’appel à la fonction Une erreur se produit lors de l’appel à la fonction

récursive lorsque en base 1, puisque les deux récursive lorsque en base 1, puisque les deux paramètres sont identiques. Ceci entraîne une série paramètres sont identiques. Ceci entraîne une série infinie d’appel à la fonction récursive.infinie d’appel à la fonction récursive.

En testant et en validant la base avant de faire appel En testant et en validant la base avant de faire appel à la fonction récursive, ceci éviterait de faire appel à à la fonction récursive, ceci éviterait de faire appel à la fonction récursive en base 1. Le test n’est effectué la fonction récursive en base 1. Le test n’est effectué qu’une seule fois puisque ce test sera valide pour qu’une seule fois puisque ce test sera valide pour tous les appels subséquents. Ceci permettra ainsi de tous les appels subséquents. Ceci permettra ainsi de posséder une fonction plus robuste.posséder une fonction plus robuste.


15

Fonction récursive pour N Fonction récursive pour N pour n’importe quelle basepour n’importe quelle base

void printIntRec( int n , int base)void printIntRec( int n , int base){{ static string DIGIT_TABLE = static string DIGIT_TABLE = “ “0123456789abcdef”;0123456789abcdef”;

if ( n if ( n >= base >= base ))printIntRec( n/base, base );printIntRec( n/base, base );

cout cout << DIGIT_TABLE[ n%base ]<< DIGIT_TABLE[ n%base ];;}}

void printInt(int n, int base)void printInt(int n, int base){{ if(base <=1 || base > MAX_BASE)if(base <=1 || base > MAX_BASE) cerr << cerr << “Impression impossible en base “ << base <<endl;“Impression impossible en base “ << base <<endl; elseelse {{ if(n < 0)if(n < 0) {{ cout << cout << ”-”;”-”; n = -n;n = -n; }} } } printIntRec(n,base)printIntRec(n,base)}}


16

III – Limitations: Fonction III – Limitations: Fonction récursive Fibonnaccirécursive Fibonnacci

long fibo (long valeur){ if (valeur <= 1) return valeur; else return(fibo(valeur-1) + fibo(valeur-2));

}

// voir main1.cpp

Soit la fonction Fibo (Fibonacci), effectuant Soit la fonction Fibo (Fibonacci), effectuant l’opération l’opération f(n) = f(n-1) + f(n-2)f(n) = f(n-1) + f(n-2)


17

Exécution de FibonnacciExécution de Fibonnacci

Soit les appels effecutés pour fibo(4) :Soit les appels effecutés pour fibo(4) :

fibo(4)fibo(4)

fibo(3)fibo(3)

fibo(2)fibo(2)

fibo(1)fibo(1) fibo(0)fibo(0)

fibo(1)fibo(1)

fibo(2)fibo(2)

fibo(0)fibo(0)fibo(1)fibo(1)


18

Danger de FibonnacciDanger de Fibonnacci

Note :Note :• Cette fonction récursive effectue plusieurs appels au même Cette fonction récursive effectue plusieurs appels au même

calcul. Par exemple pour déterminer f(n), on calcule d’abord calcul. Par exemple pour déterminer f(n), on calcule d’abord f(n-1), puis au retour de l’appel, f(n-2) est calculé. Or, dans le f(n-1), puis au retour de l’appel, f(n-2) est calculé. Or, dans le calcul de f(n-1), f(n-2) est déjà calculé!calcul de f(n-1), f(n-2) est déjà calculé!

• Ce problème s’aggrave en descendant l’arborescence, Ce problème s’aggrave en descendant l’arborescence, puisque f(n-3) sera appelé à 3 reprises : chaque appel récursif puisque f(n-3) sera appelé à 3 reprises : chaque appel récursif entraînera de plus en plus d’appel redondant. entraînera de plus en plus d’appel redondant.

• Règle 4:Règle 4: Ne jamais dupliquer le travail par la résolution d’une Ne jamais dupliquer le travail par la résolution d’une même instance d’un problème dans plusieurs appels récursifs.même instance d’un problème dans plusieurs appels récursifs.


19

IV – Arbres: introductionIV – Arbres: introduction

Définition :Définition :• Un arbre est une structure Un arbre est une structure

fondamentale et omniprésente en fondamentale et omniprésente en informatique. informatique.

• La plupart des systèmes La plupart des systèmes d’exploitation organisent leur fichiers d’exploitation organisent leur fichiers dans une structure arborescente.dans une structure arborescente.


20

DéfinitionsDéfinitions

• Arbre Arbre : Un arbre est une structure : Un arbre est une structure composée de noeuds et d'arêtes pour composée de noeuds et d'arêtes pour laquelle il n'existe qu'un seul chemin pour laquelle il n'existe qu'un seul chemin pour passer d'un noeud à un autre.passer d'un noeud à un autre.

• Racine Racine : Premier noeud d'un arbre (noeud : Premier noeud d'un arbre (noeud sans père).sans père).

• Feuille Feuille : Noeud n'ayant pas de fils.: Noeud n'ayant pas de fils.


21

Représentation d’un arbreReprésentation d’un arbre

A

C

F G

B

ED


22

V – Autres exemplesV – Autres exemples

• Exemples démontrant des méthodes Exemples démontrant des méthodes qui peuvent être implémentés non qui peuvent être implémentés non récursivement et des avantages de la récursivement et des avantages de la récursivité.récursivité.

• Ex : recherche dichotomique (binaire)Ex : recherche dichotomique (binaire)• Ex : Dessin d’une règleEx : Dessin d’une règle


23

Recherche binaire Recherche binaire (dichotomique)(dichotomique)

Idée générale :Idée générale :• La recherche d’une valeur particulière dans un tableau La recherche d’une valeur particulière dans un tableau

ordonné se fait par divisions successives du tableau en ordonné se fait par divisions successives du tableau en deux parties. Le fait que le tableau soit ordonné permet de deux parties. Le fait que le tableau soit ordonné permet de déterminer rapidement la moitié dans laquelle se trouve déterminer rapidement la moitié dans laquelle se trouve l’élément recherché.l’élément recherché.i = début –1i = début –1j = fin +1j = fin +1 Tant que i et j ne se rencontrent pasTant que i et j ne se rencontrent pas Trouver le milieu du sous-tableau courantTrouver le milieu du sous-tableau courant Si la valeur cherchée < tableau [milieu]Si la valeur cherchée < tableau [milieu] j = milieuj = milieu Si la valeur cherchée = tableau [milieu]Si la valeur cherchée = tableau [milieu] Retourne milieuRetourne milieu Si la valeur cherchée > tableau [milieu]Si la valeur cherchée > tableau [milieu] i = milieui = milieuRetourne -1Retourne -1


24

Recherche Recherche dichotomique : Exemple dichotomique : Exemple d’exécutiond’exécution

Valeur Cherchée = 17; Début = 0, Fin = 10Valeur Cherchée = 17; Début = 0, Fin = 10

00 11 22 33 44 55 66 77 88 99 1010

-2-2 55 77 99 1111 1515 1717 2020 2121 3030 3939

iijj

milieumilieu

-1-1 1111

La valeur cherchée est dans la partie gauche du tableauLa valeur cherchée est dans la partie gauche du tableauValeur cherchée = tableauValeur cherchée = tableau[milieu][milieu]Valeur cherchée > tableauValeur cherchée > tableau[milieu][milieu]

La valeur cherchée est dans la partie droite du tableauLa valeur cherchée est dans la partie droite du tableauValeur cherchée < tableauValeur cherchée < tableau[milieu][milieu]

On retourne milieuOn retourne milieu


25

Recherche binaire : Recherche binaire : programmation non-récursiveprogrammation non-récursive

int RechercheBinaire( int * Tableau, int Debut, int Fin, int RechercheBinaire( int * Tableau, int Debut, int Fin, int ValeurCherchee)int ValeurCherchee){ { int i = Debut - 1;int i = Debut - 1; int j = Fin + 1;int j = Fin + 1; while ( i+1 != j)while ( i+1 != j) { { int milieu = (i+j)/2;int milieu = (i+j)/2; if ( ValeurCherchee < Tableau[milieu])if ( ValeurCherchee < Tableau[milieu]) j = milieu;j = milieu; if (ValeurCherchee == Tableau[milieu])if (ValeurCherchee == Tableau[milieu]) return milieu;return milieu; if (ValeurCherchee > Tableau[milieu])if (ValeurCherchee > Tableau[milieu]) i = milieu;i = milieu; }} return -1;return -1;}}


26

Fonction récursive pour la Fonction récursive pour la recherche binairerecherche binairetemplate template <class Comparable><class Comparable>int binarySearch(const vector<Comparable>& a, const Comparable& x)int binarySearch(const vector<Comparable>& a, const Comparable& x) { return binarySearch(a, x, 0, a.size()-1); }{ return binarySearch(a, x, 0, a.size()-1); }

template <class Comparable>template <class Comparable>int binarySearch(const vector<Comparable>& a, const Comparable& x, int binarySearch(const vector<Comparable>& a, const Comparable& x,

int low, int high) int low, int high){{ if(low > high)if(low > high) return NOT_FOUND;return NOT_FOUND;

int mid = (low+ high)/2;int mid = (low+ high)/2;

if( a[mid] < x)if( a[mid] < x) return binarySearch(a, x, mid+1, high)return binarySearch(a, x, mid+1, high) else if( x < a[mid])else if( x < a[mid]) return binarySearch(a, x, low, mid-1);return binarySearch(a, x, low, mid-1); elseelse return mid;return mid;}}


27

VI – Sous-séquence de VI – Sous-séquence de somme maximalesomme maximale

Définition:Définition:• La technique de La technique de diviser et conquérirdiviser et conquérir

(divide-and-conquer) est une méthode de (divide-and-conquer) est une méthode de résolution de problèmes basée sur la résolution de problèmes basée sur la récursivité:récursivité:

• DiviserDiviser en plusieurs sous problèmes résolus en plusieurs sous problèmes résolus récursivement.récursivement.

• ConquérirConquérir, où la solution du problème original , où la solution du problème original est composé de la solution des sous-problèmes.est composé de la solution des sous-problèmes.


28

Sous-séquence de somme Sous-séquence de somme maximalemaximale

Définition:Définition:• Étant donnée des entiers Étant donnée des entiers

(possiblement négatifs) A(possiblement négatifs) A1, 1, AA2,. . . , 2,. . . , AAN, N,

trouver et identifier la séquence trouver et identifier la séquence correspondante à la valeur maximale correspondante à la valeur maximale de . La somme de la sous-de . La somme de la sous-séquence est nulle si tous les entiers séquence est nulle si tous les entiers sont négatifs.sont négatifs.

j

ik kA


29


Exemple:Exemple:• Soit les entiers suivants: Soit les entiers suivants: {4, -3, 5, -2, {4, -3, 5, -2,

-1, 2, 6, -2}. On divise cet ensemble-1, 2, 6, -2}. On divise cet ensemble en deux: en deux:

Première moitiéPremière moitié Deuxième Deuxième moitiémoitié

ValeursValeurs

SommesSommes

4 -3 5 -24 -3 5 -2 -1 2 6 -2-1 2 6 -2

4* 0 3 -24* 0 3 -2 -1 1 7* 5-1 1 7* 5

Sommes à partir du centre Sommes à partir du centre

(* indique la somme maximale pour chaque moitié)(* indique la somme maximale pour chaque moitié)


30


Cas possible:Cas possible:• Cas 1Cas 1: La séquence est situé dans la : La séquence est situé dans la

première moitié.première moitié.• Cas 2Cas 2: La séquence est situé dans la : La séquence est situé dans la

deuxième moitié.deuxième moitié.• Cas 3Cas 3: La séquence commence dans : La séquence commence dans

la première moitié et se termine dans la première moitié et se termine dans la deuxième moitié.la deuxième moitié.


31

Algorithme de la sous-Algorithme de la sous-séquence de somme maximaleséquence de somme maximale

Sommaire de l’algorithme:Sommaire de l’algorithme:1.1. Déterminer récursivement la sous-séquence de somme Déterminer récursivement la sous-séquence de somme

maximale uniquement dans la première moitié.maximale uniquement dans la première moitié.

2.2. Déterminer récursivement la sous-séquence de somme Déterminer récursivement la sous-séquence de somme maximale uniquement dans la deuxième moitié.maximale uniquement dans la deuxième moitié.

3.3. Avec deux boucles consécutives, déterminer la sous-Avec deux boucles consécutives, déterminer la sous-séquence de somme maximale qui débute dans la séquence de somme maximale qui débute dans la prempremiière moitié et qui termine dans la deuxième ère moitié et qui termine dans la deuxième moitié.moitié.

4.4. Choisir la somme la plus élevée des trois.Choisir la somme la plus élevée des trois.


32

Fonction récursive pour la Fonction récursive pour la sous-séquence de somme sous-séquence de somme maximalemaximale

templatetemplate<class Comparable><class Comparable>Comparable maxSubSum( const vector<Comparable> & a, int left, int right)Comparable maxSubSum( const vector<Comparable> & a, int left, int right){{ Comparable maxLeftBorderSum = 0, maxRightBorderSum = 0;Comparable maxLeftBorderSum = 0, maxRightBorderSum = 0; Comparable leftBorderSum = 0, rightBorderSum = 0;Comparable leftBorderSum = 0, rightBorderSum = 0; int center = ( left + right ) / 2;int center = ( left + right ) / 2;

if(left == right)if(left == right) return a[left] > 0 ? a[left] : 0;return a[left] > 0 ? a[left] : 0; Comparable maxLeftSum = maxSubSum(a,left,center);Comparable maxLeftSum = maxSubSum(a,left,center); Comparable maxRightSum = maxSubSum(a,center+1,right);Comparable maxRightSum = maxSubSum(a,center+1,right); for(int i=center; i>=left ;i--)for(int i=center; i>=left ;i--) {{ leftBorderSum += a[i];leftBorderSum += a[i]; if( leftBorderSum > maxLeftBorderSum )if( leftBorderSum > maxLeftBorderSum ) maxLeftBorderSum = leftBorderSum;maxLeftBorderSum = leftBorderSum; }} . . .. . .


33

for(int j=center+1; j<=right; j++)for(int j=center+1; j<=right; j++) {{ rightBorderSum += a[j];rightBorderSum += a[j]; if( rightBorderSum > maxRightBorderSum )if( rightBorderSum > maxRightBorderSum ) maxRightBorderSum = rightBorderSum;maxRightBorderSum = rightBorderSum; }}

return max3( maxLeftSum, maxRightSum, maxLeftBorderSum + return max3( maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum );maxRightBorderSum );}}

template <class Comparable>template <class Comparable>Comparable maxSubsequenceSum( const vector<Comparable> & a)Comparable maxSubsequenceSum( const vector<Comparable> & a){{ return a.size() > 0 ? maxSubSum( a, 0, a.size() – 1) : 0;return a.size() > 0 ? maxSubSum( a, 0, a.size() – 1) : 0;}}

Fonction récursive pour la Fonction récursive pour la sous-séquence de somme sous-séquence de somme maximalemaximale


34

Sous-séquence de somme Sous-séquence de somme maximale (Exemple)maximale (Exemple)

3 2 -5 -1 0 -1 2

3 2 -5 -1 0 -1 2

3 2 -5 -1 0 -1 2

2 -5 -1 0 -1 2

22

33

22 00 00 00 00

00 1122

0000 00

00

max(2,0,2+0)max(2,0,2+0)

22

max(3,2,3+2)max(3,2,3+2)

33

00 00

max(0,0,0+0)max(0,0,0+0)

00 22

max(0,2,0+2)max(0,2,0+2)

max(0,2,0+1)max(0,2,0+1)

dstjdstj


35

Sous-séquence de somme Sous-séquence de somme maximale (Exemple)maximale (Exemple)

3 2 -5 -1 0 -1 2

3 2 -5 -1 0 -1 2

3 2 -5 -1 0 -1 2

2 -5 -1 0 -1 2

22

33

22 00 00 00 00

00 1122

0000 00

00

max(2,0,2+0)max(2,0,2+0)

22

max(3,2,3+2)max(3,2,3+2)

33

00 00

max(0,0,0+0)max(0,0,0+0)

00 22

max(0,2,0+2)max(0,2,0+2)

max(0,2,0+1)max(0,2,0+1)

max(5,2,0+0max(5,2,0+0)=5)=5

dstjdstj


36

VII – BacktrackingVII – Backtracking

Problématique :Problématique :• Pour résoudre certains types de problèmes, il peut être Pour résoudre certains types de problèmes, il peut être

souvent utile de procéder à l'exploration systématique des souvent utile de procéder à l'exploration systématique des différentes solutions possibles. Il est donc essentiel de différentes solutions possibles. Il est donc essentiel de développer des techniques algorithmiques qui permettent une développer des techniques algorithmiques qui permettent une telle exploration.telle exploration.

Idée générale pour le calcul du trajet du robot:Idée générale pour le calcul du trajet du robot:• Il s'agit de concevoir un algorithme qui permet à un robot de Il s'agit de concevoir un algorithme qui permet à un robot de

trouver un chemin menant à la sortie d'un labyrinthe. Pour ce trouver un chemin menant à la sortie d'un labyrinthe. Pour ce faire le robot explore systématiquement les quatre directions faire le robot explore systématiquement les quatre directions vers lesquelles il peut se déplacer. De plus, afin d'éviter que vers lesquelles il peut se déplacer. De plus, afin d'éviter que le robot ne se retrouve sur des cases déjà explorées chacune le robot ne se retrouve sur des cases déjà explorées chacune de celles-ci seront marquées à mesure qu'elles sont visitées. de celles-ci seront marquées à mesure qu'elles sont visitées. C'est de façon récursive que les cases faisant partie du C'est de façon récursive que les cases faisant partie du chemin seront identifiées.chemin seront identifiées.


37

Algorithme du retour-Algorithme du retour-arrièrearrière


38

Plan du sitePlan du site

N

EO

S

Légende

: point de départ

: point d’arrivée

: mur ou obstache

E

S

0

A B C D E F G H I

S

E1

2

3

4

5

6


39

Programmation du trajet Programmation du trajet d’un robot mobiled’un robot mobile

#define Y 9 /* Les dimensions du labyrinthe */#define Y 9 /* Les dimensions du labyrinthe */#define X 7#define X 7char laby[X][Y] = { {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},char laby[X][Y] = { {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'}, {'X', ' ', ' ', 'X', ' ', ' ', ' ', ' ', 'X'},{'X', ' ', ' ', 'X', ' ', ' ', ' ', ' ', 'X'}, {'X', ' ', 'X', 'X', ' ', 'X', 'X', ' ', 'X'},{'X', ' ', 'X', 'X', ' ', 'X', 'X', ' ', 'X'}, {'X', ' ', ' ', ' ', ' ', ' ', 'X', 'X', 'X'},{'X', ' ', ' ', ' ', ' ', ' ', 'X', 'X', 'X'}, {'X', 'X', 'X', ' ', 'X', ' ', 'X', ' ', 'X'},{'X', 'X', 'X', ' ', 'X', ' ', 'X', ' ', 'X'}, {'X', 's', ' ', ' ', ' ', ' ', ' ', ' ', 'X'},{'X', 's', ' ', ' ', ' ', ' ', ' ', ' ', 'X'}, {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'}};{'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'}};main()main(){{ int i, j;int i, j; bool Parcours(int x, int y);bool Parcours(int x, int y); if (Parcours(1,1)) {if (Parcours(1,1)) { // Imprimer le résultat de la recherche// Imprimer le résultat de la recherche for (i = 0; i < X; i++, cout<<endl)for (i = 0; i < X; i++, cout<<endl) for (j = 0; j < Y; j++)for (j = 0; j < Y; j++) cout<<laby[i][j]; }cout<<laby[i][j]; } elseelse cout<<"Il n'existe aucun chemin.\n";cout<<"Il n'existe aucun chemin.\n";}}


40

Programmation du trajet Programmation du trajet d’un robot mobile (suite)d’un robot mobile (suite)

bool Parcours(int x, int y)bool Parcours(int x, int y){{ if (laby[x][y] == 's') { /* on a trouvé la sortie */if (laby[x][y] == 's') { /* on a trouvé la sortie */ laby[x][y] = 'S';laby[x][y] = 'S'; return true;return true; } else if (laby[x][y] == ' ') { /* la case est libre */} else if (laby[x][y] == ' ') { /* la case est libre */ laby[x][y] = 'o'; /* marquer la case visitée */laby[x][y] = 'o'; /* marquer la case visitée */ if (Parcours(x-1, y)) /* Parcours nord */if (Parcours(x-1, y)) /* Parcours nord */ return(true);return(true); else if (Parcours(x, y+1)) /* Parcours est */else if (Parcours(x, y+1)) /* Parcours est */ return(true);return(true); else if (Parcours(x+1, y)) /* Parcours sud */else if (Parcours(x+1, y)) /* Parcours sud */ return(true);return(true); else if (Parcours(x, y-1)) /* Parcours ouest */else if (Parcours(x, y-1)) /* Parcours ouest */ return(true);return(true); elseelse laby[x][y] = '-'; /* on laisse une marque */laby[x][y] = '-'; /* on laisse une marque */ } } return false;return false;}}


41

Retour en arrière - exerciceRetour en arrière - exercice

• Quel est le chemin parcouru? Combien de retours en arrière?

• Utiliser des appels récursifs et l’ordre d’appel suivant:• Nord• Sud• Est• Ouest

0 1 2 3 4 5 6 7 8 9

A

B S

C

D

E

F EG

H

I

J


42

Retour en arrière - réponseRetour en arrière - réponse0 1 2 3 4 5 6 7 8 9

A

B

C

D

E

F

G

H

I

J

X

E

S

oo

o

o

oo X

X

o

o

o

o

o

o o o

o

oX

o

o o

o

o o o

o

o

o

o o

oX

Xo

o

Documents

INF1101 Algorithmes et structures de données1 Cours 5 La récursivité