Algorithme: Exercice R0120112016

• Définir la récursivité.
• Reconnaître et identifier des algorithmes récursifs.
• Faire appel à des fonctions récursives pour résoudre certains problèmes.

Pour chacun des exercices suivants :

• Proposer une analyse modulaire au problème,
• Analyser chacun des modules envisagés précédemment
• Déduire les algorithmes correspondants,
• Traduire la solution en un programme Pascal.

Convertir, en Pascal, la procédure itérative ci-dessous en une procédure récursive
Procedure Compter ;
Var i : integer ;
Begin
For i :=1 to 10 do
Writeln(‘Bac 2011’) ;
End ;

Ecrire une fonction récursive nommée Somme_Chiffre qui retourne la somme des chiffres d’un nombre N donné.
Exemple : (417 4+1+7 = 12)

• Ecrire une fonction récursive nommée Chiffre_Droite qui détermine le K^ième chiffre à partir de la droite d’un entier n>0.
• Exemples : le 3^ème chiffre de 89752 est 7
• Le 5^ème chiffre de 21327 est 2

• On appelle palindrome une chaîne de caractères qui donne la même chaîne selon que l’on la lise de gauche à droite ou inversement. Autrement dit, le premier caractère est égal au dernier, le deuxième caractère est égal à l’avant dernier, etc.
• Une définition récursive d’un palindrome est :
• La chaîne vide est un palindrome ;
• La chaîne constituée d’un seul caractère est un palindrome ;
• aXb est un palindrome si a = b et si X est un palindrome. (Exemple : “ABCBA” ; A=A et “BCB” est un palindrome).
• Écrire une fonction récursive nommée Palindrome qui vérifie si une chaîne donnée est palindrome.

• Écrire une fonction récursive Inverse qui permet de lire une phrase ou un mot et de l’écrire à l’envers, à partir du dernier caractère rentré.
• Exemple :
• Miroir, qui est la plus belle ? ? elleb sulp al tse iuq ,rioriM

• Écrire une fonction récursive nommée anag qui détermine si deux chaînes sont anagrammes.
• Deux chaînes ch1, ch2 sont dites anagrammes, si les lettres qui composent la 1^er chaîne existent tous dans la 2^ème chaîne.
• Exemple : ch1 = chien et ch2 = niche

• La fonction d’Ackermann f est définie, pour x et y entiers naturels, par :

[latex]
f(x,y) =\left
\{
\begin{array}{r c l}
y+1 & si&x=0 \\
f(x − 1, 1) si&y = 0 \\
f(x-1,f(x,y− 1))& si&x \ne y\ne 0
\end{array}
\right.
[/latex]

Calculer f(2,3).

La suite de Fibonnacci est définie par :
[latex]
f_{n} =\left
\{
\begin{array}{r c l}
1 & si&n=0 \\
1 &si&n = 1 \\
f_{n-1}+f_{n-2} & pour& n>2
\end{array}
\right.
[/latex]

Calculer f(7).

• 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

• Écrire un programme récursif qui affiche tout le contenu d’un tableau T de taille n.