TP 8

On cherche à écrire quelques fonctions récursives courantes.

Fonctions usuelles

1. Écrire une fonction récursive permettant de calculer x à la puissance n.
2. Proposez une implémentation de la recherche dichotomique de façon récursive dans un tableau d'entiers.
3. Implémentez une fonction récursive donnant le n^ème élément de la suite de Fibonacci
4. Soient a et b deux entiers, avec a≥b ; l'algorithme d'Euclide calcule le PGCD de a et b en utilisant le fait que PGCD(a,b) = PGCD(b,r) où r est le reste de la division euclidienne de a par b. Proposez une implémentation récursive du PGCD.
5. Proposez une fonction permettant d'inverser les éléments d'un tableau d'entiers de façon récursive.

Sur les listes chaînées

6. Donnez un algorithme récursif qui affiche tous les éléments d'une liste.
7. Donnez une fonction récursive permettant de calculer la taille d'une liste (sans utiliser le nombre d'éléments).
8. Écrire le code de la fonction permettant de supprimer un élément d'une liste de façon récursive.
9. Donnez un algorithme permettant d'ajouter un élément à sa place dans une liste triée.