Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Objectifs • Définir la récursivité • Reconnaître et identifier des algorithmes

Objectifs • Définir la récursivité • Reconnaître et identifier des algorithmes récursifs • Résoudre des problèmes faisant appel à la récursivité Plan du chapitre I- Introduction II- Définitions et principes III- Applications Retenons Exercices Lecture Chapitre 2 pitre 2 La récursivité Ce document PDF a été édité via Icecream PDF Editor. Passez à la version PRO pour retirer le filigrane. La récursivité Chapitre 2 74 Activité 1 Question 1 : Proposez une analyse, puis déduisez l’algorithme d’une fonction permettant de calculer la factorielle d’un entier n. Comment appelle t-on le procédé utilisé dans ce traitement ? Tableau de déclaration des objets : Objets Type / Nature Rôle F Entier Long Contenant la factorielle de n i Entier non signé (Mot) Compteur I. Introduction Analyse de la fonction Factorielle Résultat : Factorielle Traitement : La factorielle est obtenue après : Une initialisation (F ← 1), Ensuite, une structure itérative complète (Pour i de 2 à n Faire) contenant l’instruction : F ←F * i Algorithme de la fonction Factorielle 0) Fonction Factorielle (n : Entier non signé) : Entier Long 1) F ←1 2) Pour i de 2 à n Faire F←F * i Fin Pour 3) Factorielle ←F 4) Fin Factorielle Question 2 : Pouvez vous proposer un procédé différent pour trouver la valeur de la factorielle de n ? Il s’agit d’un procédé itératif pour calculer n! Ce document PDF a été édité via Icecream PDF Editor. Passez à la version PRO pour retirer le filigrane. La récursivité 75 Et si pour résoudre un problème, on réduisait sa taille ? Dans certains cas, la solution d’un problème peut se ramener à résoudre le même problème de taille plus réduite, qui lui-même pourra se ramener à résoudre le même problème de taille encore plus petite ... jusqu'à aboutir à la résolution d’un problème élémentaire. ? Donnez la formule mathématique de la factorielle de n n ! = n * (n-1) * (n-2) * (n-3) * … * 1 et 0 ! = 1 ⎧ ⎨ ⎩ ou encore factorielle (n) = n * (n-1) * (n-2) * (n-3) * … * 1 Formule 1 et factorielle (0) = 1 ⎧ ⎨ ⎩ factorielle (n) = n * factorielle (n-1) Formule 2 et factorielle (0) = 1 ⎧ ⎨ ⎩ ⎧ ⎨ ⎩ ⎧ ⎨ ⎩ Explications : ? Remplacez la partie colorée de la Formule1 donnée ci-dessus par une expression équi- valente utilisant la fonction factorielle Constatations : Pour définir factorielle (n) au niveau de la Formule 1, nous avons utilisé un traitement itératif. Pour définir factorielle (n) au niveau de la Formule 2, nous avons utilisé un autre procédé répétitif : nous avons appelé la même fonction sur d’autres données plus simples (factorielle (n-1)). Ce procédé s’appelle Traitement Récursif. Exemple : Pour calculer factorielle (4) ou 4!, nous procédons ainsi : 1ère étape : 4 ≠0 alors Factorielle (4) = 4 * Factorielle (4-1) = 4 * Factorielle (3) 2ème étape : 3 ≠0 alors Factorielle (3) = 3 * Factorielle (3-1) = 3 * Factorielle (2) d’où Factorielle (4) = 4 * 3 * Factorielle (2) 3ème étape : 2 ≠0 alors Factorielle (2) = 2 * Factorielle (2-1) = 2 * Factorielle (1) d’où Factorielle (4) = 4 * 3 * 2 * Factorielle (1) Ce document PDF a été édité via Icecream PDF Editor. Passez à la version PRO pour retirer le filigrane. Chapitre 2 76 4ème étape : 1 ≠0 alors Factorielle (1) = 1 * Factorielle (1-1) = 1 * Factorielle (0) d’où Factorielle (4) = 4 * 3 * 2 * 1 * Factorielle (0) 5ème étape : La valeur 0 est rejointe, c’est le cas particulier qui provoquera l’arrêt des étapes du calcul de la factorielle, alors Factorielle (0) = 1 D’où Factorielle (4) = 4 * 3 * 2 * 1 * 1 Le résultat final = 24 Conclusion : Voici la solution récursive de la fonction Factorielle : 0) Fonction Factorielle (n : Entier non signé) : Entier Long 1) Si (n = 0) Alors Factorielle ←1 Sinon Factorielle ←n * Factorielle (n-1) Fin Si 2) Fin Factorielle Constatations : La solution récursive comporte : L’appel récursif en changeant la valeur du paramètre. Dans l’exemple de la fonction Factorielle, le paramètre est décrémenté de 1 à chaque appel, (Factorielle ←n * Factorielle (n-1)) La condition d’arrêt de l’appel récursif. En effet, nous arrêtons le traitement quand n devient égal à 0 (Si n = 0 Alors Factorielle ←1) Question 3 : Traduisez et testez la solution du problème permettant d’afficher la factorielle d’un entier n donné, en utilisant la version récursive de la fonction Factorielle. Enregistrez votre programme sous le nom Fact_rec. PROGRAM Fact_rec; Uses Crt; Var n : Word; Function Factorielle (m : Word) : LongInt; Begin If (m = 0) Then Factorielle := 1 Else Factorielle := m * Factorielle (m - 1); End; Ce document PDF a été édité via Icecream PDF Editor. Passez à la version PRO pour retirer le filigrane. La récursivité 77 {Programme Principal} BEGIN Write ('n = '); ReadLn (n); Write ('n! = ', Factorielle (n)); END. Activité 2 Question 1 : Proposez une analyse, puis déduisez l’algorithme itératif d’une fonction permettant de vérifier si une chaîne de caractères CH est un palindrome. Nous appellons "palindrome" un mot ou une phrase qui se lit de la même façon dans les deux sens (de gauche à droite et de droite à gauche ). Exemples : radar, rotor, été. Analyse de la fonction Palindrome Résultat : Palindrome, Traitement : Le résultat booléen de la fonction Palindrome est obtenu après : [i ←1], Ensuite, une structure itérative à condition d’arrêt (Répéter … Jusqu’à) vérifiant les actions suivantes : À chaque itération, nous comparons deux à deux les caractères symétriques de CH relatifs à une position i (Verif ←(ch[i] = ch[Long (ch) – i + 1])). Nous arrêtons la répétition à la première différence (Verif = Faux) ou lorsque nous atteignons les caractères du milieu (i > Long (ch) Div 2). Algorithme itératif de la fonction Palindrome 0) Fonction Palindrome (ch : Chaîne) : Booléen 1) i ←1 Répéter Verif ←(ch[i] = ch[Long (ch) – i + 1]) i ←i + 1 Jusqu’à (i > Long (ch) Div 2) Ou (Verif = Faux) 2) Palindrome ←Verif 3) Fin Palindrome Tableau de codification des objets locaux Objets Type / Nature Rôle i Octet Compteur Verif Booléen Tester l'état de ch (Palindrome ou non) Ce document PDF a été édité via Icecream PDF Editor. Passez à la version PRO pour retirer le filigrane. Chapitre 2 78 Question 2 : Dégagez une relation récursive permettant de vérifier si une chaîne de caractères CH est un palindrome. ➣Essayons de dégager cette relation à partir d’un premier exemple (ch = "radar", de longueur = 5) : 1ère étape : Long ("radar") = 5 ; comme 5 n’est pas inférieur à 2, et comme les caractères extrêmes de la chaîne "radar" sont identiques = "r" alors, Palindrome ("radar") = Palindrome ("ada") 2ème étape : Long ("ada") = 3 ; comme 3 n’est pas inférieur à 2, et comme les caractères extrêmes de la chaîne "ada" sont identiques = "a" alors, Palindrome ("ada") = Palindrome ("d") 3ème étape : Long ("d") = 1 ; comme 1 est inférieur à 2, c’est le cas particulier qui provoquera l’arrêt des étapes de la vérification si ch est palindrome ou non, alors Palindrome = Vrai Dans cet exemple, ch est un palindrome car on a obtenu une chaîne formée d’un seul caractère ("d") sans rencontrer de i vérifiant ch[i] ≠ch[Long (ch)-i+1]. ➣ Réessayons avec l’exemple suivant (ch = "exemple", de longueur = 7) : 1ère étape : Long ("exemple") = 7 ; comme 7 n’est pas inférieur à 2, et comme les caractères extrêmes de la chaîne "exemple" sont identiques = "e" alors, Palindrome ("exemple") = Palindrome ("xempl") 2ème étape : Long ("xempl") = 5 ; comme 5 n’est pas inférieur à 2, et comme les caractères extrêmes de la chaîne "xempl" sont différents ("x"≠"l") alors, Palindrome = Faux Dans cet exemple, ch n’est pas un palindrome car ch[2] ≠ch[7-2+1] (puisque "x" ≠"l") Remarques : Un mot d’un seul caractère est un palindrome, sinon il l’est dès que ses caractères extrêmes sont les mêmes et le mot restant est aussi un palindrome. ➣ d’où, la relation récursive suivante : Si Longueur (ch) < 2 alors ch est un palindrome Sinon si ch[1] = ch[Long (ch)] alors Palindrome (ch) = Palindrome (ch sans ses premier et dernier caractères) Sinon ch n’est pas un palindrome. Ce document PDF a été édité via Icecream PDF Editor. Passez à la version PRO pour retirer le filigrane. La récursivité 79 Question 3 : Déduisez l’algorithme récursif de la fonction Palindrome. Algorithme : 0) Fonction Palindrome (ch : Chaîne) : Booléen 1) Si Long (ch) < 2 Alors Palindrome ←Vrai Sinon Si ch[1] = ch[Long (ch)] Alors Palindrome ← Palindrome (Sous_chaîne uploads/Litterature/ chapitre-2-la-recursivite.pdf