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)$

Correction
​
def recursive_sum (n: int) -> int:

    """
        This function calculates the sum of all positive integers less than or equal to n.
        For example, the sum up to 5 is 5 + 4 + 3 + 2 + 1 = 15.
        In:
            * n: The number up to which sum is to be calculated.
        Out:
            * The sum up to n.
    """

    # Make sure that n has a correct value
    assert n >= 0

    # Base case
    if n == 0:
        return 0

    # Recursive call
    return n + recursive_sum(n - 1)



# Don't forget to test your function
assert recursive_sum(4) == 10

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)$

Correction
​
def product (n: int, p: int) -> int:

    """
        This function calculates the product of n and p.
        The product of n and p is the sum of p added to itself n times.
        For example, the product of 3 and 4 is 4 + 4 + 4 = 12.
        In:
            * n: The number of times p is to be added to itself.
            * p: The number to be added to itself n times.
        Out:
            * The product of n and p.
    """

    # Make sure that n and p have correct values
    assert n >= 0
    assert p >= 0

    # Base case
    if n == 0:
        return 0

    # Recursive call
    return p + product(n - 1, p)



# Don't forget to test your function
assert product(4, 5) == 20
assert product(4, 0) == 0
assert product(0, 5) == 0

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$.

Correction
​
def modulo (n: int, p: int) -> int:

    """
        This function calculates the modulo of n and p.
        The modulo of n and p is the remainder of the division of n by p.
        For example, the modulo of 10 and 3 is 1.
        In:
            * n: The number to be divided by p.
            * p: The number by which n is to be divided.
        Out:
            * The modulo of n and p.
    """

    # Make sure that n and p have correct values
    assert n >= 0
    assert p > 0

    # Base case
    if n < p:
        return n

    # Recursive call
    return modulo(n - p, p)



# Don't forget to test your function
assert modulo(4, 5) == 4
assert modulo(10, 3) == 1

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.

Correction
​
def sum_digits (n: int) -> int:

    """
        This function calculates the sum of the digits of a number n.
        For example, the sum of the digits of 123 is 1 + 2 + 3 = 6.
        In:
            * n: The number whose digits are to be summed.
        Out:
            * The sum of the digits of n.
    """

    # Make sure that n has a correct value
    assert n >= 0

    # Base case
    if n < 10:
        return n

    # Recursive call
    return n % 10 + sum_digits(n // 10)



# Don't forget to test your function
assert sum_digits(0) == 0
assert sum_digits(8) == 8
assert sum_digits(42) == 6
assert sum_digits(123456789) == 45

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.

Correction
​
# Needed imports
from typing import List



def minimum (l: List[int]) -> int:

    """
        This function calculates the minimum value in a list l.
        For example, the minimum value in [3, 1, 4, 1, 5, 9, 2, 6, 5] is 1.
        In:
            * l: The list in which the minimum value is to be found.
        Out:
            * The minimum value in l.
    """

    # Make sure that l is not empty
    assert len(l) > 0

    # Base case
    if len(l) == 1:
        return l[0]

    # Recursive call
    current_min = minimum(l[1:])
    if current_min < l[0]:
        return current_min
    else:
        return l[0]



# Don't forget to test your function
assert minimum([1]) == 1
assert minimum([-5, 10, 0]) == -5
assert minimum([0, -5, 10]) == -5
assert minimum([0, 10, -5]) == -5

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.

Correction
​
# Needed imports
from typing import List



def count (l: List[int], e: int) -> int:

    """
        This function calculates the number of times a value e appears in a list l.
        For example, the value 1 appears 2 times in [3, 1, 4, 1, 5, 9, 2, 6, 5].
        In:
            * l: The list in which the value e is to be counted.
            * e: The value to be counted in l.
        Out:
            * The number of times e appears in l.
    """

    # Base case
    if len(l) == 0:
        return 0

    # Recursive call
    current_count = count(l[1:], e)
    if l[0] == e:
        return current_count + 1
    else:
        return current_count



# Don't forget to test your function
assert count([1], 0) == 0
assert count([], 0) == 0
assert count([1], 1) == 1
assert count([2, 1, 5, 7, 9, 1], 1) == 2
assert count([2, 1, 5, 7, 9, 1], 8) == 0

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.

Correction
​
def is_palindrome (s: str) -> bool:

    """
        This function checks if a string s is a palindrome.
        A palindrome is a string that reads the same forwards and backwards.
        For example, "racecar" is a palindrome.
        In:
            * s: The string to be checked if it is a palindrome.
        Out:
            * True if s is a palindrome, False otherwise.
    """

    # Base case
    if len(s) <= 1:
        return True

    # Recursive call
    return s[0] == s[-1] and is_palindrome(s[1:-1])



# Don't forget to test your function
assert is_palindrome("laval")
assert is_palindrome("a")
assert not is_palindrome("guingamp")
assert is_palindrome("tattarrattat")

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é.

Correction
​
def binomial_coefficient (n: int, k: int) -> int:

    """
        This function calculates the binomial coefficient of n and k.
        The binomial coefficient of n and k is the number of ways to choose k elements from a set of n elements.
        In:
            * n: The number of elements in the set.
            * k: The number of elements to be chosen.
        Out:
            * The binomial coefficient of n and k.
    """

    # Verify arguments
    assert k >= 0
    assert n >= k

    # Base case
    if k == 0 or k == n:
        return 1
    
    # Recursive call
    return binomial_coefficient(n - 1, k) + binomial_coefficient(n - 1, k - 1)



# Tests for binomial_coefficient
assert binomial_coefficient(5, 1) == 5
assert binomial_coefficient(5, 5) == 1
assert binomial_coefficient(10, 4) == 210
assert binomial_coefficient(8, 5) == 56
def factorial (n: int) -> int:

    """
        This function calculates the factorial of a number n.
        The factorial of a number n is the product of all positive integers less than or equal to n.
        For example, the factorial of 5 is 5 * 4 * 3 * 2 * 1 = 120.
        The factorial of 0 is 1.
        In:
            * n: The number whose factorial is to be calculated.
        Out:
            * The factorial of n.
    """

    # Verify arguments
    assert n >= 0

    # Base case
    if n == 0:
        return 1
    
    # Recursive call
    return n * factorial(n - 1)



def binomial_coefficient (n: int, k: int) -> int:

    """
        This function calculates the binomial coefficient of n and k.
        The binomial coefficient of n and k is the number of ways to choose k elements from a set of n elements.
        In:
            * n: The number of elements in the set.
            * k: The number of elements to be chosen.
        Out:
            * The binomial coefficient of n and k.
    """

    # Verify arguments
    assert k >= 0
    assert n >= k

    # Using the recursive factorial
    return factorial(n) // (factorial(k) * factorial(n - k))



# Tests for factorial
assert factorial(0) == 1
assert factorial(1) == 1
assert factorial(5) == 120

# Tests for binomial_coefficient
assert binomial_coefficient(5, 1) == 5
assert binomial_coefficient(5, 5) == 1
assert binomial_coefficient(10, 4) == 210
assert binomial_coefficient(8, 5) == 56

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 ordonnée 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.

Correction
​
# Needed imports
from typing import List



def dicho_contains (l: List[int], e: int) -> bool:

    """
        This function checks if a value e is in a sorted list l using the dichotomic search.
        The dichotomic search is a search algorithm that divides the search interval in half at each step.
        In:
            * l: The sorted list in which the value e is to be found.
            * e: The value to be found in l.
        Out:
            * True if e is in l, False otherwise.
    """

    # Base case 1
    if len(l) == 0:
        return False

    # Base case 2
    if len(l) == 1:
        return l[0] == e

    # Recursive call
    mid = len(l) // 2
    return dicho_contains(l[:mid], e) or dicho_contains(l[mid:], e)



# Don't forget to test your function
assert dicho_contains([0, 5, 4, 3], 4)
assert not dicho_contains([0, 5, 4, 3], 1)
assert dicho_contains([0, 5, 3], 5)
assert not dicho_contains([0, 5, 3], 4)
assert dicho_contains([0], 0)
assert not dicho_contains([0], 1)
assert not dicho_contains([], 2)

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 ?

Correction

Si la liste est ordonnée, on peut exploiter cette propriété pour améliorer l’efficacité de la recherche.

Voici une version modifiée de dicho_contains s’appuyant sur cette propriété.

​
# Needed imports
from typing import List



def dicho_contains (l: List[int], e: int) -> bool:

    """
        This function checks if a value e is in a sorted list l using the dichotomic search.
        The dichotomic search is a search algorithm that divides the search interval in half at each step.
        In:
            * l: The sorted list in which the value e is to be found.
            * e: The value to be found in l.
        Out:
            * True if e is in l, False otherwise.
    """

    # Base case
    if len(l) == 0:
        return False

    # Recursive call
    mid = len(l) // 2
    if l[mid] == e:
        return True
    if l[mid] < e:
        return dicho_contains(l[mid + 1:], e)
    return dicho_contains(l[:mid], e)



# Don't forget to test your function
assert dicho_contains([0, 5, 4, 3], 4)
assert not dicho_contains([0, 5, 4, 3], 1)
assert dicho_contains([0, 5, 3], 5)
assert not dicho_contains([0, 5, 3], 4)
assert dicho_contains([0], 0)
assert not dicho_contains([0], 1)
assert not dicho_contains([], 2)

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.

Correction
​
# Needed imports
from typing import List



def count_coin_changes (amount: int, coins: List[int]) -> int:

    """
        This function calculates the number of ways to make change for a given amount using a list of coins.
        In:
            * amount: The amount for which change is to be made.
            * coins:  The list of coins available to make change.
        Out:
            * The number of ways to make change for the given amount.
    """

    # Base case 1
    if amount == 0:
        return 1

    # Base case 2
    if amount < 0 or len(coins) == 0:
        return 0
    
    # Recursive call
    with_first_coin = count_coin_changes(amount - coins[0], coins)
    without_it = count_coin_changes(amount, coins[1:])
    return with_first_coin + without_it



# Tests for count_coin_changes
assert count_coin_changes(0, [1, 2, 3]) == 1
assert count_coin_changes(1, [1, 2, 3]) == 1
assert count_coin_changes(2, [1, 2, 3]) == 2
assert count_coin_changes(3, [1, 2, 3]) == 3
assert count_coin_changes(4, [1, 2, 3]) == 4
assert count_coin_changes(10, [1, 2, 3]) == 14

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.