pdf - e-book - archive

2.7  Récursivité

2.7.1  Sous-programmes récursifs

Tous les sous-programmes dans les exercices ci-dessous doivent être rédigés de façon récursive, ils ne doivent pas contenir de boucle.

Exercice 1 Compte à rebours

Écrire une procédure affichant un compte à rebours en partant du nombre passé en paramètre.

Exercice 2 Somme

Écrire une fonction retournant la somme de deux nombres entiers positifs passés en paramètre sans les additionner. Vous n’utiliserez que des incrémentations et des décrémentations.

Exercice 3 Factorielle

Écrire une fonction retournant la factorielle du nombre passé en paramètre.

Exercice 4 Produit

Écrire une fonction retournant le produit de deux nombres entiers passés en paramètre sans les multiplier.

Exercice 5 Série arithmétique

Écrire une fonction retournant la somme des n premiers entiers (où n est passé en paramètre).

Exercice 6 Puissance

Écrire une fonction retournant bn (où b et n sont tous deux passés en paramètre).

Exercice 7 Nombre de chiffres

Écrire une fonction retournant le nombre de chiffres d’un entier n passé en paramètre. Ne pas convertir le nombre en chaîne de caractères !

Exercice 8 p-ème chiffre

Écrire une fonction retournant le p-ième chiffre d’un entier n en partant de la droite. Si par exemple n=13489765123 et p=4, alors la fonction retourne 5 car il s’agit du 4 chiffre de n en partant des unités.

Exercice 9 Somme des chiffres

Écrire une fonction retournant la somme des chiffres d’un entier n passé en paramètre.

2.7.2  Morceaux choisis

Exercice 10 Recherche par dichotomie

Écrire une fonction recherche(t[], x, i, j : entier) : booleen retournant vrai si et seulement si il existe un élément du tableau t qui soit égal à x et dont l’indice se trouve entre i et j. On suppose que le tableau t est trié.

Exercice 11 Suite de Fibonacci

Écrire une fonction permettant de calculer le n-ème terme de la suite de Fibonacci définie par u0 = 0, u1 = 1 et un = un−1 + nn − 2. Est-ce efficace pour de grandes valeurs de n ? Est-il possible de rédiger un algorithme itératif ayant de meilleures performances ?

Exercice 12 Tri fusion

Écrire une procédure appliquant la méthode du tri fusion à un tableau passé en paramètre.

Exercice 13 Belle marquise...

Écrire une procédure affichant toutes les permutations de Belle marquise, vos beaux yeux me font mourir d’amour.