Activités pratiques : fonctions récursives

Duration1h15

Pré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 :

  1. Déterminer d’abord le(s) cas de base où il n’y a pas d’appel récursif.
  2. Puis, déterminer les instructions à exécuter lors des appels récursifs.
  3. 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.

Important

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 :

$$\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$$

Assurez-vous que votre code est correct en l’exécutant avec différentes entrées et en vérifiant les résultats.

Aide

Pour résoudre ce problème, vous pouvez vous inspirer de la fonction factorielle.

$\text{sum}(n) = n + \text{sum}(n-1)$

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.

Aide

Pour résoudre ce problème, vous pouvez transformer le produit en une somme.

$\text{product}(n, p) = n + \text{product}(n, p-1)$

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.

Aide

Pour résoudre ce problème, vous pouvez remarquer que le reste de la division euclidienne est le nombre qui reste lorsque vous soustrayez p de n jusqu’à ce que n soit inférieur à p.

$\text{modulo}(n, p) = modulo(n - p, p) $ si $n \geq p$ sinon $n$.

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.

Aide

Voici quelques opérations sur les listes qui peuvent vous aider :

  • l[0] pour accéder au premier élément de la liste.
  • l[1:] pour accéder à la liste sans le premier élément.

Pour résoudre ce problème, vous pouvez comparer le premier élément de la liste avec le minimum des éléments restants de la liste.

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

    La fonction suppose que l est triée, afin de ne faire l’appel récursif que sur la moitié correcte de la liste à chaque itération. Si on casse cette propriété, il y a une chance que e apparaisse dans la moitié qui n’est pas recherchée. Par conséquent, la fonction peut ne pas le trouver, et retourner false au lieu du true attendu.

  • Pourquoi le cas de base 2 a-t-il été supprimé ?

    Correction

    Lorsque l’on divise la liste en deux moitiés, on vérifie si le milieu contient e. Il n’y a donc pas d’intérêt à le rechercher à nouveau là-bas.

    On pourrait argumenter que c’est pareil d’inclure e dans, par exemple, la liste la plus à gauche. Cependant, pourquoi continuer à faire des appels récursifs jusqu’à un élément restant, si on trouve directement e lors de la division de la liste en moitiés ?

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.