Practical activity

Duration1h15

Présentation & objectifs

Voici une liste d’exercices pour expérimenter les 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.
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, nous vous suggérons de refaire l’exercice avec ces outils activés. Suivre ces deux étapes améliorera vos compétences à la fois fondamentalement et pratiquement.

De plus, nous vous fournissons les solutions aux exercices. Assurez-vous de les consulter uniquement après avoir une solution aux exercices, à des fins de comparaison ! Même si vous êtes sûr que votre solution est correcte, veuillez les regarder, car elles fournissent parfois des éléments supplémentaires que vous auriez pu manquer.

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.

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
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * 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.
     *
     * @param n The number up to which sum is to be calculated.
     * @return The sum up to n.
     */
    public static int recursiveSum(int n) {
        // Make sure that n has a correct value
        assert n >= 0;

        // Base case
        if (n == 0) {
            return 0;
        }

        // Recursive call
        return n + recursiveSum(n - 1);
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Don't forget to test your function
        assert recursiveSum(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.

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
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * 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.
     *
     * @param n The number of times p is to be added to itself.
     * @param p The number to be added to itself n times.
     * @return The product of n and p.
     */
    public static int product(int n, int 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);
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // 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.

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
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * 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.
     *
     * @param n The number to be divided by p.
     * @param p The number by which n is to be divided.
     * @return The modulo of n and p.
     */
    public static int modulo(int n, int 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);
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // 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
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * 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.
     *
     * @param n The number whose digits are to be summed.
     * @return The sum of the digits of n.
     */
    public static int sumDigits(int n) {
        // Make sure that n has a correct value
        assert n >= 0;

        // Base case
        if (n < 10) {
            return n;
        }

        // Recursive call
        return n % 10 + sumDigits(n / 10);
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Don't forget to test your function
        assert sumDigits(0) == 0;
        assert sumDigits(8) == 8;
        assert sumDigits(42) == 6;
        assert sumDigits(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.

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
// Needed imports
import java.util.List;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * 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.
     *
     * @param l The list in which the minimum value is to be found.
     * @return The minimum value in l.
     */
    public static int minimum(List<Integer> l) {
        // Make sure that l is not empty
        assert !l.isEmpty();

        // Base case
        if (l.size() == 1) {
            return l.get(0);
        }

        // Recursive call
        int currentMin = minimum(l.subList(1, l.size()));
        if (currentMin < l.get(0)) {
            return currentMin;
        } else {
            return l.get(0);
        }
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Don't forget to test your function
        assert minimum(List.of(1)) == 1;
        assert minimum(List.of(-5, 10, 0)) == -5;
        assert minimum(List.of(0, -5, 10)) == -5;
        assert minimum(List.of(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
// Needed imports
import java.util.List;
import java.util.ArrayList;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * 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].
     *
     * @param l The list in which the value e is to be counted.
     * @param e The value to be counted in l.
     * @return The number of times e appears in l.
     */
    public static int count(List<Integer> l, int e) {
        // Base case
        if (l.size() == 0) {
            return 0;
        }

        // Recursive call
        int currentCount = count(l.subList(1, l.size()), e);
        if (l.get(0) == e) {
            return 1 + currentCount;
        } else {
            return currentCount;
        }
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Don't forget to test your function
        assert count(List.of(1), 0) == 0;
        assert count(new ArrayList<>(), 0) == 0;
        assert count(List.of(1), 1) == 1;
        assert count(List.of(2, 1, 5, 7, 9, 1), 1) == 2;
        assert count(List.of(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) 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. 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")
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * 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.
     *
     * @param s The string to be checked if it is a palindrome.
     * @return True if s is a palindrome, False otherwise.
     */
    public static boolean isPalindrome(String s) {
        // Base case
        if (s.length() <= 1) {
            return true;
        }

        // Recursive call
        return s.charAt(0) == s.charAt(s.length() - 1) && isPalindrome(s.substring(1, s.length() - 1));
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Don't forget to test your function
        assert isPalindrome("laval");
        assert isPalindrome("a");
        assert !isPalindrome("guingamp");
        assert isPalindrome("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)!} $$

Une relation de récurrence existe pour calculer le coefficient binomial, connue sous le nom de règle de Pascal.

É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
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * 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.
     *
     * @param n The number of elements in the set.
     * @param k The number of elements to be chosen.
     * @return The binomial coefficient of n and k.
     */
    public static int binomialCoefficient(int n, int k) {
        // Verify arguments
        assert k >= 0;
        assert n >= k;

        // Base case
        if (k == 0 || k == n) {
            return 1;
        }

        // Recursive call
        return binomialCoefficient(n - 1, k) + binomialCoefficient(n - 1, k - 1);
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Tests for binomialCoefficient
        assert binomialCoefficient(5, 1) == 5;
        assert binomialCoefficient(5, 5) == 1;
        assert binomialCoefficient(10, 4) == 210;
        assert binomialCoefficient(8, 5) == 56;
    }

}
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * 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.
     *
     * @param n The number whose factorial is to be calculated.
     * @return The factorial of n.
     */
    public static int factorial(int n) {
        // Verify arguments
        assert n >= 0;

        // Base case
        if (n == 0) {
            return 1;
        }

        // Recursive call
        return n * factorial(n - 1);
    }


    /**
     * 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.
     *
     * @param n The number of elements in the set.
     * @param k The number of elements to be chosen.
     * @return The binomial coefficient of n and k.
     */
    public static int binomialCoefficient(int n, int k) {
        // Verify arguments
        assert k >= 0;
        assert n >= k;

        // Base case
        if (k == 0 || k == n)
            return 1;

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


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Tests for factorial
        assert factorial(0) == 1;
        assert factorial(1) == 1;
        assert factorial(5) == 120;

        // Tests for binomialCoefficient
        assert binomialCoefficient(5, 1) == 5;
        assert binomialCoefficient(5, 5) == 1;
        assert binomialCoefficient(10, 4) == 210;
        assert binomialCoefficient(8, 5) == 56;
    }

}

9 — Toutes les permutations d’une liste

Les permutations d’une liste sont les listes qui contiennent les mêmes éléments dans un ordre différent, y compris la liste initiale elle-même. Dans cet exercice, nous ne considérerons que les listes dont tous les éléments sont distincts.

Il y a $n!$ permutations d’une liste de $n$ éléments.

Écrivez une fonction récursive all_permutations(l) qui retourne la liste de toutes les permutations de l. Vous devez vous assurer que les paramètres de votre fonction vérifient les conditions et que votre code est testé et documenté.

Correction
​
# Needed imports
from typing import List



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

    """
        This function calculates all permutations of a list l.
        A permutation is an arrangement of all elements of a set in a particular order.
        In:
            * l: The list of elements to be permuted.
        Out:
            * The list of all permutations of l.
    """

    # Let's define a helper function to define permutations and store them when they are complete
    def _all_permutations (l: List[int], current_permutation: List[int], result: List[List[int]]) -> None:

        # Base case: if the list is empty, we have found a permutation
        if len(l) == 0:
            result.append(current_permutation)

        # Recursive case: we will try to append each element of the list to the current permutation
        else:
            for i in range(len(l)):
                next_permutation = current_permutation + [l[i]]
                remaining_elements = l[:i] + l[i+1:]
                _all_permutations(remaining_elements, next_permutation, result)

    # Start the recursion to fill the result list
    result = []
    _all_permutations(l, [], result)
    return result



# Tests for all_permutations
assert sorted(all_permutations([])) == [[]]
assert sorted(all_permutations([1])) == [[1]]
assert sorted(all_permutations([1, 2])) == [[1, 2], [2, 1]]
assert sorted(all_permutations([1, 2, 3])) == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
// Needed imports
import java.util.ArrayList;
import java.util.List;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This function calculates all permutations of a list l.
     * A permutation is an arrangement of all elements of a set in a particular order.
     * 
     * @param l The list of elements to be permuted.
     * @return  The list of all permutations of l.
     */
    public static List<List<Integer>> allPermutations(List<Integer> l) {
        // Start the recursion to fill the result list
        List<List<Integer>> result = new ArrayList<>();
        _allPermutations(l, new ArrayList<>(), result);
        return result;
    }

    /**
     * Helper function to define permutations and store them when they are complete.
     * 
     * @param l                  The remaining elements to permute.
     * @param currentPermutation The current permutation being built.
     * @param result             The list to store the complete permutations.
     */
    private static void _allPermutations(List<Integer> l, List<Integer> currentPermutation, List<List<Integer>> result) {
        // Base case: if the list is empty, we have found a permutation
        if (l.isEmpty()) {
            result.add(new ArrayList<>(currentPermutation));
        } 
        // Recursive case: we will try to append each element of the list to the current permutation
        else {
            for (int i = 0; i < l.size(); i++) {
                List<Integer> nextPermutation = new ArrayList<>(currentPermutation);
                nextPermutation.add(l.get(i));
                List<Integer> remainingElements = new ArrayList<>(l.subList(0, i));
                remainingElements.addAll(l.subList(i + 1, l.size()));
                _allPermutations(remainingElements, nextPermutation, result);
            }
        }
    }

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Helper function to sort the list of lists
        java.util.Comparator<List<Integer>> listComparator = (a, b) -> {
            int size = Math.min(a.size(), b.size());
            for (int i = 0; i < size; i++) {
                if (!a.get(i).equals(b.get(i))) {
                    return a.get(i) - b.get(i);
                }
            }
            return a.size() - b.size();
        };

        // Tests for allPermutations
        List<List<Integer>> result;

        result = allPermutations(new ArrayList<>());
        result.sort(listComparator);
        assert result.equals(List.of(List.of()));

        result = allPermutations(List.of(1));
        result.sort(listComparator);
        assert result.equals(List.of(List.of(1)));

        result = allPermutations(List.of(1, 2));
        result.sort(listComparator);
        assert result.equals(List.of(List.of(1, 2), List.of(2, 1)));

        result = allPermutations(List.of(1, 2, 3));
        result.sort(listComparator);
        assert result.equals(List.of(
            List.of(1, 2, 3), List.of(1, 3, 2), List.of(2, 1, 3), List.of(2, 3, 1), List.of(3, 1, 2), List.of(3, 2, 1)
        ));
    }

}

Maintenant, écrivez une fonction qui retourne uniquement les permutations qui satisfont la condition suivante : la somme des nb premiers éléments est inférieure ou égale à une valeur threshold. On suppose que la liste ne contient que des entiers positifs.

La condition doit être évaluée pendant la construction des permutations. Autrement dit, elle ne doit pas être appliquée en post-traitement pour filtrer les permutations invalides. En effet, faire cela après serait inutile pour gagner du temps car toutes les permutations auraient déjà été calculées.

Correction
​
# Needed imports
from typing import List



def some_permutations (l: List[int], nb: int, threshold: int) -> List[List[int]]:

    """
        This function calculates some permutations of a list l.
        A permutation is an arrangement of all elements of a set in a particular order.
        Kept permutations have a sum of the first nb elements lower than a given threshold.
        In:
            * l:         The list of elements to be permuted.
            * nb:        Number of first elements for which to check the sum.
            * threshold: Maximum sum allowed.
        Out:
            * The list of all permutations of l.
    """

    # Let's define a helper function to define permutations and store them when they are complete
    def _some_permutations (l: List[int], current_permutation: List[int], result: List[List[int]]) -> None:

        # Base case: if the list is empty, we have found a permutation
        if len(l) == 0:
            result.append(current_permutation)

        # Recursive case: we will try to append each element of the list to the current permutation
        else:
            for i in range(len(l)):
                next_permutation = current_permutation + [l[i]]
                remaining_elements = l[:i] + l[i+1:]
                if sum(next_permutation[:nb]) <= threshold:
                    _some_permutations(remaining_elements, next_permutation, result)

    # Start the recursion to fill the result list
    result = []
    _some_permutations(l, [], result)

    # Make sure to return a list of lists
    if len(result) == 0:
        return [[]]
    return result



# Tests for some_permutations
assert sorted(some_permutations([], 1, 2)) == [[]]
assert sorted(some_permutations([1], 1, 1)) == [[1]]
assert sorted(some_permutations([1], 1, 0)) == [[]]
assert sorted(some_permutations([1, 2], 1, 1)) == [[1, 2]]
assert sorted(some_permutations([1, 2], 1, 3)) == [[1, 2], [2, 1]]
assert sorted(some_permutations([1, 2, 3], 1, 3)) == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
assert sorted(some_permutations([1, 2, 3], 2, 4)) == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [3, 1, 2]]
assert sorted(some_permutations([1, 2, 3], 3, 6)) == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
assert sorted(some_permutations([1, 7], 1, 6)) == [[1,7]]
assert sorted(some_permutations([1, 7], 2, 6)) == [[]]
assert sorted(some_permutations([1, 2, 3, 4], 2, 5)) == [[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [4, 1, 2, 3], [4, 1, 3, 2]]
// Needed imports
import java.util.ArrayList;
import java.util.List;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This function calculates some permutations of a list l.
     * A permutation is an arrangement of all elements of a set in a particular order.
     * Kept permutations have a sum of the first nb elements lower than a given threshold.
     * 
     * @param l         The list of elements to be permuted.
     * @param nb        Number of first elements for which to check the sum.
     * @param threshold Maximum sum allowed.
     * @return          The list of valid permutations of l.
     */
    public static List<List<Integer>> somePermutations(List<Integer> l, int nb, int threshold) {
        // Start the recursion to fill the result list
        List<List<Integer>> result = new ArrayList<>();
        _somePermutations(l, new ArrayList<>(), result, nb, threshold);

        // Make sure to return a list of lists
        if (result.isEmpty()) {
            result.add(new ArrayList<>());
        }
        return result;
    }

    /**
     * Helper function to generate permutations and store them when they are complete.
     * 
     * @param l                  The remaining elements to permute.
     * @param currentPermutation The current permutation being built.
     * @param result             The list to store valid permutations.
     * @param nb                 Number of first elements for which to check the sum.
     * @param threshold          Maximum sum allowed for the first nb elements.
     */
    private static void _somePermutations(List<Integer> l, List<Integer> currentPermutation, List<List<Integer>> result, int nb, int threshold) {
        // Base case: if the list is empty, we have found a permutation
        if (l.isEmpty()) {
            result.add(new ArrayList<>(currentPermutation));
        } 
        // Recursive case: we will try to append each element of the list to the current permutation
        else {
            for (int i = 0; i < l.size(); i++) {
                List<Integer> nextPermutation = new ArrayList<>(currentPermutation);
                nextPermutation.add(l.get(i));
                List<Integer> remainingElements = new ArrayList<>(l.subList(0, i));
                remainingElements.addAll(l.subList(i + 1, l.size()));

                // Check if the sum of the first nb elements is below the threshold
                if (sumFirstElements(nextPermutation, nb) <= threshold) {
                    _somePermutations(remainingElements, nextPermutation, result, nb, threshold);
                }
            }
        }
    }

    /**
     * Helper function to calculate the sum of the first nb elements in a list.
     * 
     * @param l  The list of integers.
     * @param nb The number of elements to sum.
     * @return   The sum of the first nb elements.
     */
    private static int sumFirstElements(List<Integer> l, int nb) {
        int sum = 0;
        for (int i = 0; i < nb && i < l.size(); i++) {
            sum += l.get(i);
        }
        return sum;
    }

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Helper function to sort the list of lists
        java.util.Comparator<List<Integer>> listComparator = (a, b) -> {
            int size = Math.min(a.size(), b.size());
            for (int i = 0; i < size; i++) {
                if (!a.get(i).equals(b.get(i))) {
                    return a.get(i) - b.get(i);
                }
            }
            return a.size() - b.size();
        };

        // Tests for somePermutations
        List<List<Integer>> result;

        result = somePermutations(new ArrayList<>(), 1, 2);
        result.sort(listComparator);
        assert result.equals(List.of(List.of()));

        result = somePermutations(List.of(1), 1, 1);
        result.sort(listComparator);
        assert result.equals(List.of(List.of(1)));

        result = somePermutations(List.of(1), 1, 0);
        result.sort(listComparator);
        assert result.equals(List.of(List.of()));

        result = somePermutations(List.of(1, 2), 1, 1);
        result.sort(listComparator);
        assert result.equals(List.of(List.of(1, 2)));

        result = somePermutations(List.of(1, 2), 1, 3);
        result.sort(listComparator);
        assert result.equals(List.of(List.of(1, 2), List.of(2, 1)));

        result = somePermutations(List.of(1, 2, 3), 1, 3);
        result.sort(listComparator);
        assert result.equals(List.of(
            List.of(1, 2, 3), List.of(1, 3, 2), List.of(2, 1, 3), List.of(2, 3, 1), List.of(3, 1, 2), List.of(3, 2, 1)
        ));

        result = somePermutations(List.of(1, 2, 3), 2, 4);
        result.sort(listComparator);
        assert result.equals(List.of(
            List.of(1, 2, 3), List.of(1, 3, 2), List.of(2, 1, 3), List.of(3, 1, 2)
        ));

        result = somePermutations(List.of(1, 2, 3), 3, 6);
        result.sort(listComparator);
        assert result.equals(List.of(
            List.of(1, 2, 3), List.of(1, 3, 2), List.of(2, 1, 3), List.of(2, 3, 1), List.of(3, 1, 2), List.of(3, 2, 1)
        ));

        result = somePermutations(List.of(1, 7), 1, 6);
        result.sort(listComparator);
        assert result.equals(List.of(List.of(1, 7)));

        result = somePermutations(List.of(1, 7), 2, 6);
        result.sort(listComparator);
        assert result.equals(List.of(List.of()));

        result = somePermutations(List.of(1, 2, 3, 4), 2, 5);
        result.sort(listComparator);
        assert result.equals(List.of(
            List.of(1, 2, 3, 4), List.of(1, 2, 4, 3), List.of(1, 3, 2, 4), List.of(1, 3, 4, 2), List.of(1, 4, 2, 3), List.of(1, 4, 3, 2),
            List.of(2, 1, 3, 4), List.of(2, 1, 4, 3), List.of(2, 3, 1, 4), List.of(2, 3, 4, 1),
            List.of(3, 1, 2, 4), List.of(3, 1, 4, 2), List.of(3, 2, 1, 4), List.of(3, 2, 4, 1),
            List.of(4, 1, 2, 3), List.of(4, 1, 3, 2)
        ));
    }

}

10 — Optimisez vos solutions

Ce que vous pouvez faire maintenant est d’utiliser des outils d’IA tels que GitHub Copilot ou ChatGPT, soit pour générer la solution, soit pour améliorer la première solution que vous avez trouvée ! Essayez de faire cela pour tous les exercices ci-dessus, pour voir les différences avec vos solutions.

Pour aller plus loin

11 — 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.

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)
// Needed imports
import java.util.List;
import java.util.ArrayList;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */

public class Main {

    /**
     * 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.
     *
     * @param l The sorted list in which the value e is to be found.
     * @param e The value to be found in l.
     * @return True if e is in l, False otherwise.
     */
    public static boolean dichoContains(List<Integer> l, int e) {
        // Base case 1
        if (l.isEmpty()) {
            return false;
        }

        // Base case 2
        if (l.size() == 1) {
            return l.get(0) == e;
        }

        // Recursive call
        int mid = l.size() / 2;
        return dichoContains(l.subList(0, mid), e) || dichoContains(l.subList(mid, l.size()), e);
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Don't forget to test your function
        assert dichoContains(List.of(0, 5, 4, 3), 4);
        assert !dichoContains(List.of(0, 5, 4, 3), 1);
        assert dichoContains(List.of(0, 5, 3), 5);
        assert !dichoContains(List.of(0, 5, 3), 4);
        assert dichoContains(List.of(0), 0);
        assert !dichoContains(List.of(0), 1);
        assert !dichoContains(new ArrayList<>(), 2);
    }

}

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)
// Needed imports
import java.util.List;
import java.util.ArrayList;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */

public class Main {

    /**
     * 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.
     *
     * @param l The sorted list in which the value e is to be found.
     * @param e The value to be found in l.
     * @return True if e is in l, False otherwise.
     */
    public static boolean dichoContains(List<Integer> l, int e) {
        // Base case
        if (l.isEmpty()) {
            return false;
        }

        // Recursive call
        int mid = l.size() / 2;
        if (l.get(mid) == e) {
            return true;
        }
        if (l.get(mid) < e) {
            return dichoContains(l.subList(mid + 1, l.size()), e);
        }
        return dichoContains(l.subList(0, mid), e);
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Don't forget to test your function
        assert dichoContains(List.of(0, 5, 4, 3), 4);
        assert !dichoContains(List.of(0, 5, 4, 3), 1);
        assert dichoContains(List.of(0, 5, 3), 5);
        assert !dichoContains(List.of(0, 5, 3), 4);
        assert dichoContains(List.of(0), 0);
        assert !dichoContains(List.of(0), 1);
        assert !dichoContains(new ArrayList<>(), 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 ?

12 — 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
// Needed imports
import java.util.List;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This function calculates the number of ways to make change for a given amount using a list of coins.
     *
     * @param amount The amount for which change is to be made.
     * @param coins  The list of coins available to make change.
     * @return The number of ways to make change for the given amount.
     */
    public static int countCoinChanges(int amount, List<Integer> coins) {
        // Base case 1
        if (amount == 0) {
            return 1;
        }

        // Base case 2
        if (amount < 0 || coins.isEmpty()) {
            return 0;
        }

        // Recursive call
        int withFirstCoin = countCoinChanges(amount - coins.get(0), coins);
        int withoutFirstCoin = countCoinChanges(amount, coins.subList(1, coins.size()));
        return withFirstCoin + withoutFirstCoin;
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Tests for countCoinChanges
        assert countCoinChanges(0, List.of(1, 2, 3)) == 1;
        assert countCoinChanges(1, List.of(1, 2, 3)) == 1;
        assert countCoinChanges(2, List.of(1, 2, 3)) == 2;
        assert countCoinChanges(3, List.of(1, 2, 3)) == 3;
        assert countCoinChanges(4, List.of(1, 2, 3)) == 4;
        assert countCoinChanges(10, List.of(1, 2, 3)) == 14;
    }

}

Maintenant, écrivez une fonction récursive list_coin_changes(amount, coins) qui liste toutes les 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, les façons d’atteindre la valeur amount = 3 avec coins = [1,2] sont [[1, 1, 1], [1, 2]]. Ici encore, [2, 1] est équivalent à [1, 2] et une seule des deux combinaisons apparaît.

Correction
​
# Needed imports
from typing import List



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

    """
        This function appends a value e to all sublists of a list of sublists l.
        In:
            * e: The value to be appended to all sublists.
            * l: The list of sublists to which e is to be appended.
        Out:
            * The list of sublists with e appended to all sublists.
    """

    # Add to all sublists
    result = []
    for sublist in l:
        result.append([e] + sublist)
    return result



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

    """
        This function calculates all possible 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 list of all possible ways to make change for the given amount.
    """

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

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



# Tests for append_all
assert append_all(5, [[]]) == [[5]]
assert append_all(5, [[1], []]) == [[5, 1], [5]]
assert append_all(5, [[1], [1, 2], []]) == [[5, 1], [5, 1 , 2], [5]]

# Tests for list_coin_changes
assert list_coin_changes(0, [1, 2, 3]) == [[]]
assert list_coin_changes(1, [1, 2, 3]) == [[1]]
assert list_coin_changes(2, [1, 2, 3]) == [[1, 1], [2]]
assert list_coin_changes(3, [1, 2, 3]) == [[1, 1, 1], [1, 2], [3]]
assert list_coin_changes(4, [1, 2, 3]) == [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2]]
assert list_coin_changes(10, [1, 2, 3]) == [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 3, 3], [1, 1, 1, 2, 2, 3], [1, 1, 2, 2, 2, 2], [1, 1, 2, 3, 3], [1, 2, 2, 2, 3], [1, 3, 3, 3], [2, 2, 2, 2, 2], [2, 2, 3, 3]]
// Needed imports
import java.util.ArrayList;
import java.util.List;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */

public class Main {

    /**
     * This function appends a value e to all sublists of a list of sublists l.
     *
     * @param e The value to be appended to all sublists.
     * @param l The list of sublists to which e is to be appended.
     * @return The list of sublists with e appended to all sublists.
     */
    public static List<List<Integer>> appendAll(Integer e, List<List<Integer>> l) {
        // Add to all sublists
        List<List<Integer>> res = new ArrayList<>();
        for (List<Integer> sublist : l) {
            List<Integer> tmp = new ArrayList<>(sublist);
            tmp.add(0, e);
            res.add(tmp);
        }
        return res;
    }

    /**
     * This function calculates all possible ways to make change for a given amount using a list of coins.
     *
     * @param amount The amount for which change is to be made.
     * @param coins  The list of coins available to make change.
     * @return The list of all possible ways to make change for the given amount.
     */
    public static List<List<Integer>> listCoinChanges(int amount, List<Integer> coins) {
        // Base case 1
        if (amount == 0) {
            return List.of(new ArrayList<>());
        }

        // Base case 2
        if (amount < 0 || coins.isEmpty()) {
            return new ArrayList<>();
        }

        // Recursive call
        List<List<Integer>> withFirstCoin = listCoinChanges(amount - coins.get(0), coins);
        List<List<Integer>> withoutFirstCoin = listCoinChanges(amount, coins.subList(1, coins.size()));
        List<List<Integer>> result = new ArrayList<>(appendAll(coins.get(0), withFirstCoin));
        result.addAll(withoutFirstCoin);
        return result;
    }


    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Tests for appendAll
        assert appendAll(5, List.of(new ArrayList<>())).equals(List.of(List.of(5)));
        assert appendAll(5, List.of(List.of(1), new ArrayList<>())).equals(List.of(List.of(5, 1), List.of(5)));
        assert appendAll(5, List.of(List.of(1), List.of(1, 2), new ArrayList<>())).equals(List.of(List.of(5, 1), List.of(5, 1, 2), List.of(5)));

        // Tests for listCoinChanges
        assert listCoinChanges(0, List.of(1, 2, 3)).equals(List.of(new ArrayList<>()));
        assert listCoinChanges(1, List.of(1, 2, 3)).equals(List.of(List.of(1)));
        assert listCoinChanges(2, List.of(1, 2, 3)).equals(List.of(List.of(1, 1), (List.of(2))));
        assert listCoinChanges(3, List.of(1, 2, 3)).equals(List.of(List.of(1, 1, 1), List.of(1, 2), List.of(3)));
        assert listCoinChanges(4, List.of(1, 2, 3)).equals(List.of(List.of(1, 1, 1, 1), List.of(1, 1, 2), List.of(1, 3), List.of(2, 2)));
        assert listCoinChanges(10, List.of(1, 2, 3)).equals(List.of(List.of(1, 1, 1, 1, 1, 1, 1, 1, 1, 1), List.of(1, 1, 1, 1, 1, 1, 1, 1, 2), List.of(1, 1, 1, 1, 1, 1, 1, 3), List.of(1, 1, 1, 1, 1, 1, 2, 2), List.of(1, 1, 1, 1, 1, 2, 3), List.of(1, 1, 1, 1, 2, 2, 2), List.of(1, 1, 1, 1, 3, 3), List.of(1, 1, 1, 2, 2, 3), List.of(1, 1, 2, 2, 2, 2), List.of(1, 1, 2, 3, 3), List.of(1, 2, 2, 2, 3), List.of(1, 3, 3, 3), List.of(2, 2, 2, 2, 2), List.of(2, 2, 3, 3)));
    }

}

Pour aller plus loin

13 — 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.