EXERCICE X

Récursivité

1. Utiliser la fonction récursive donnée au dessus et montrer la suite de Fibonacci pour un nombre n donné.

Remarque :  La suite de Fibonacci est : 1, 1, 2, 3, 5, 8, 13, 21, …

Expression récursive du problème : Fn = Fn – 1 + Fn – 2

Condition d’arrêt : F0 = F1 = 1

Convergence (vers la condition d’arrêt):

Si n = 1 ou n = 0, alors on a « convergé »!

Si n > 1, alors les soustractions à l’étape suivante nous approche de n = 1 et n = 0

Donc si n est un entier non - négatif ça converge!

int fibonacci(int n)

{ if (n < 0) /* hypothese de convergence : n = 0 */

exit(1);

if ( n == 0 || n == 1)

return 1; /* condition d’arret */

else /* appels recursifs */

return fibonacci(n - 2) + fibonacci(n - 1);

}

2. Faire une fonction Bool palindrome(char * mot, int longueur) récursive pour vérifier q’un mot donne est palindrome. Utiliser cette fonction dans main.

Remarque : Un palindrome est un mot qui peut être lu de la même manière de gauche à droite ou de droite à gauche.

1. La récursion :

<ch, L> est un palindrome si :

ch [0] == ch [L-1] et

<ch+1, L-2> est un palindrome.

2. Les conditions d'arrêt :

1er cas : un seul caractère (L=1) -> VRAI

2e cas : une chaîne vide (L=0) -> VRAI

3e cas : si ch [0] != ch [L-1] -> FAUX (supposant que L >= 0)

3. La convergence :

Si n = 0 ou n = 1 ou ch[0] != ch[L-1], on a converge !

Sinon l’appel récursif diminue de 2 la longueur de la

chaîne, donc on approche des conditions d’arrêt.

3. Faire une fonction Bool egale(char * mot1, char *mot2) récursive pour faire la comparaison de deux chaîne. Utiliser cette fonction dans main.

Remarque:

Egal(mot1, mot2) <=> *mot1 = *mot2 ET Egale(mot1 + 1,mot2 + 1)