Activités pratiques : fonctions récursives
Duration1h15Présentation & objectifs
Voici une liste d’exercices pour expérimenter la construction de fonctions récursives.
Lors de la conception d’une fonction récursive, vous devez toujours :
- Déterminer d’abord le(s) cas de base où il n’y a pas d’appel récursif.
- Puis, déterminer les instructions à exécuter lors des appels récursifs.
- S’assurer que ces instructions atteignent le(s) cas de base.
Avant de vous lancer dans l’implémentation des solutions aux exercices, il est fortement conseillé de réfléchir collectivement sur papier à l’algorithme récursif.
Le but de cette séance est de vous aider à maîtriser des notions importantes en informatique. Un assistant de programmation intelligent tel que GitHub Copilot, que vous avez peut-être déjà installé, pourra vous fournir une solution à ces exercices uniquement à partir d’un nom de fichier judicieusement choisi.
Pour l’entraînement, nous vous conseillons de désactiver ces outils dans un premier temps.
À la fin de l’activité pratique, vous pouvez refaire quelques exercices avec ces outils activés. Vous pourrez ainsi comparer votre solution avec celle proposée par l’assistant de programmation et voir en quoi elle est différente. Suivre ces deux étapes améliorera vos compétences à la fois fondamentalement et pratiquement.
Contenu de l’activité
1 — Somme des nombres naturels
Écrivez une fonction récursive recursive_sum(n)
où $n \in \mathbb{N}$ qui calcule la somme des n
premiers nombres naturels.
L’objectif est d’apprendre à écrire des fonctions récursives, vous n’êtes donc pas autorisé à utiliser une fonction sum
intégrée, ni à utiliser la formule suivante :
Assurez-vous que votre code est correct en l’exécutant avec différentes entrées et en vérifiant les résultats.
2 — Produit de deux nombres naturels
Écrivez une fonction récursive product(n, p)
où $n,p \in \mathbb{N}^2$ qui calcule le produit de n
et p
.
Vous n’êtes pas autorisé à utiliser l’opération de multiplication.
Encore une fois, assurez-vous que votre code est correct en l’exécutant avec différentes entrées et en vérifiant les résultats.
3 — L’opération modulo
Écrivez une fonction récursive modulo(n, p)
où $n \in \mathbb{N}$ et $p \in \mathbb{N}^*$ qui calcule le reste de la division euclidienne de n
par p
.
Vous n’êtes pas autorisé à utiliser l’opérateur modulo ni la division.
Encore une fois, assurez-vous que votre code est correct en l’exécutant avec différentes entrées et en vérifiant les résultats.
4 — La somme des chiffres d’un nombre naturel
Écrivez une fonction récursive sum_digits(n)
où $n \in \mathbb{N}$ qui calcule la somme des chiffres composant n
.
Quelques indices :
- Isolez un chiffre et retirez-le de
n
. - Commencez par le chiffre le plus à droite.
Encore une fois, assurez-vous que votre code est correct en l’exécutant avec différentes entrées et en vérifiant les résultats.
5 — Trouver l’élément minimum d’une liste
Écrivez une fonction récursive minimum(l)
qui retourne le plus petit entier dans l
, où l
est une liste non vide d’entiers.
Vous n’êtes pas autorisé à utiliser la fonction min
.
Encore une fois, assurez-vous que votre code est correct en l’exécutant avec différentes entrées et en vérifiant les résultats.
6 — Compter le nombre d’occurrences d’un élément
Écrivez une fonction récursive count(l, e)
qui retourne le nombre d’occurrences de l’élément e
dans une liste l
d’entiers.
Encore une fois, assurez-vous que votre code est correct en l’exécutant avec différentes entrées et en vérifiant les résultats.
7 — Vérifier si un mot est un palindrome
Écrivez une fonction récursive is_palindrome(word)
, où word
est une chaîne de caractères (str
), qui retourne true si un mot est un palindrome, false sinon.
Pour aller plus loin, vous pouvez adapter le code pour gérer des phrases, c’est-à-dire des chaînes de caractères contenant plusieurs mots séparés par des espaces. Dans ce cas, vous devez ignorer les espaces, la ponctuation et la capitalisation.
Encore une fois, assurez-vous que votre code est correct en l’exécutant avec différentes entrées et en vérifiant les résultats.
8 — Calcul d’un coefficient binomial
Un coefficient binomial est défini par un couple d’entiers $n \geq k \geq 0$ et s’écrit ${n\choose k}$ (noté $ C^{k}_{n}$ en français). Rappel :
$$ {n\choose k} = \frac{n!}{k!(n-k)!} $$La formule de Pascal établit une relation de récurrence pour calculer le coefficient binomial.
Écrivez une fonction récursive binomial_coefficient(n, k)
qui calcule ${n\choose k}$.
Vous devez vous assurer que les paramètres de votre fonction vérifient les conditions et que votre code est testé et documenté.
Pour aller plus loin
9 — Vérifier si une liste contient un élément
Écrivez une fonction récursive dicho_contains(l, e)
qui retourne true si une liste l
contient l’entier e
, false sinon.
Vous devez utiliser une approche dichotomique. La recherche dichotomique est un algorithme de recherche qui divise l’intervalle de recherche en deux à chaque étape.
Encore une fois, assurez-vous que votre code est correct en l’exécutant avec différentes entrées et en vérifiant les résultats.
Essayez de répondre aux questions suivantes :
-
Que se passe-t-il si la liste donnée en paramètre n’est pas ordonnée ?
Correction -
Pourquoi le cas de base 2 a-t-il été supprimé ?
Correction
10 — Nombre de façons de rendre la monnaie
Écrivez une fonction récursive count_coin_changes(amount, coins)
qui compte le nombre de façons d’atteindre une valeur amount
en additionnant uniquement les valeurs appartenant à la liste coins
.
Toutes les pièces sont des nombres naturels non nuls et peuvent être utilisées autant de fois que nécessaire.
L’ordre dans lequel les pièces sont utilisées n’a pas d’importance.
Par exemple, le nombre de façons d’atteindre la valeur amount = 3
avec coins = [1, 2]
est 2 : [1, 1, 1]
et [1, 2]
.
Ici, [2, 1]
est équivalent à [1, 2]
et une seule des deux combinaisons est considérée.
Pour aller plus loin
11 — Récursion terminale
Vous pouvez essayer de rendre toutes les fonctions ci-dessus récursives terminales. Consultez à nouveau l’article sur la récursion pour plus de détails sur la manière de le faire.