Practical activity

Duration1h15

Presentation & objectives

Below is a list of exercises for experimenting with recursive functions.

When designing a recursive function, you always have to:

  1. First, determine the base case(s) where there is no recursive call.
  2. Then, determine the instructions to be executed during recursive calls.
  3. Make sure these instructions reach the base case(s).
Important

For this lab, we advise you to deactivate GiHub Copilot and AI code generation tools. You can try to do the exercises again with these tools afterwards for comparison.

Important

We provide you the solutions to the exercises. Make sure to check them only after you have a solution to the exercises, for comparison purpose! Even if you are sure your solution is correct, please have a look at them, as they sometimes provide additional elements you may have missed.

Activity contents

1 — Sum of natural numbers

Write a recursive function recursive_sum(n) where $n \in \mathbb{N}$ that computes the sum of the first n natural numbers.

The goal is to learn how to write recursive functions, so you are not allowed to use a built-in sum function, or to use the following formula:

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

Make sure that your code is correct by running it with different inputs and checking the results.

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 — Product of two natural numbers

Write a recursive function product(n, p) where $n,p \in \mathbb{N}^2$ that computes the product of n and p.

You are not allowed to use the multiplication operation.

Again, make sure that your code is correct by running it with different inputs and checking the results.

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 — The modulo operation

Write a recursive function modulo(n, p) where $n \in \mathbb{N}$ and $p \in \mathbb{N}^*$ that calculates the remainder of the Euclidean division of n by p.

You are not allowed to use the modulo operator or division.

Again, make sure that your code is correct by running it with different inputs and checking the results.

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 — The sum of the digits of a natural number

Write a recursive function sum_digits(n) where $n \in \mathbb{N}$ that calculates the sum of the digits composing n.

A few hints:

  • Isolate a digit and remove it from n.
  • Start with the rightmost digit.

Again, make sure that your code is correct by running it with different inputs and checking the results.

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 — Find the minimum element of a list

Write a recursive function minimum(l) that returns the smallest integer in l, where l is a non empty list of integers.

You are not allowed to use the min function.

Again, make sure that your code is correct by running it with different inputs and checking the results.

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
/**
 * 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.
 */

// Needed imports
import java.util.List;

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 — Count the number of occurrences of an element

Write a recursive function count(l, e) that returns the number of occurrences of the element e in a list l of integers.

Again, make sure that your code is correct by running it with different inputs and checking the results.

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
/**
 * 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.
 */

// Needed imports
import java.util.List;
import java.util.ArrayList;

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 — Check if a word is a palindrome

Write a recursive function is_palindrome(word) that returns true if a word is a palindrome, false otherwise.

To go further, you can adapt the code to deal with sentences. In that case, you must ignore the spaces, punctuation and capitalization.

Again, make sure that your code is correct by running it with different inputs and checking the results.

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 — Computing a binomial coefficient

A binomial coefficient is defined by a pair of integers $n \geq k \geq 0$ and is written ${n\choose k}$ (denoted $ C^{k}_{n}$ in French). Remind that:

$$ {n\choose k} = \frac{n!}{k!(n-k)!} $$

A recurrence relation exists to compute the binomial coefficient, known as the Pascal’s rule.

Write a recursive function binomial_coefficient(n, k) that computes ${n\choose k}$. You have to make sure that the parameters of your function verify the conditions and that your code is tested and documented.

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 — All permutations of a list

Permutations of a list are the lists that contain the same elements in a different order, including the initial list itself. In this exercice, we will only consider lists in which all elements are distinct.

There are $n!$ permutations of a list of $n$ elements.

Write a recursive function all_permutations(l) which returns the list of all permutations of l. You have to make sure that the parameters of your function verify the conditions and that your code is tested and documented.

Correction
​
# Needed imports
from typing import List, Tuple



def extract (l: List[int], i: int) -> Tuple[int, List[int]]:

    """
        This function extracts the value at index i from a list l.
        In:
            * l: The list from which the value at index i is to be extracted.
            * i: The index of the value to be extracted.
        Out:
            * A tuple with the value at index i and the list without the value at index i.
    """

    # Verify arguments
    assert 0 <= i < len(l)

    # Extract element i
    return l[i], l[:i] + l[i+1:]



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

    # Verify arguments
    assert len(l) == len(set(l))

    # Base case
    if len(l) <= 1:
        return [l]
    
    # Recursive call
    result = []
    for i in range(len(l)):
        e, sub = extract(l, i)
        result += append_all(e, all_permutations(sub))
    return result



# Tests for extract
assert extract([1, 2, 3], 0) == (1, [2, 3])
assert extract([1, 2, 3], 1) == (2, [1, 3])
assert extract([1, 2, 3], 2) == (3, [1, 2])
assert extract([1], 0) == (1, [])

# 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 all_permutations
assert all_permutations([]) == [[]]
assert all_permutations([1]) == [[1]]
assert all_permutations([1, 2]) == [[1, 2], [2, 1]]
assert all_permutations([1, 2, 3]) == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 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.
 */

// Needed imports
import java.util.ArrayList;
import java.util.List;
import java.util.HashSet;

public class Main {

    /**
     * Unlike Python, a Java method can only return a single value.
     * Here, using a record allows you to return a pair of values encapsulated in a single element, a Tuple.
     *
     * @see https://docs.oracle.com/en/java/javase/16/language/records.html
     */
    public record Tuple(Integer e, List<Integer> l) {
    }


    /**
     * This function extracts the value at index i from a list l.
     *
     * @param l The list from which the value at index i is to be extracted.
     * @param i The index of the value to be extracted.
     * @return A tuple with the value at index i and the list without the value at index i.
     */
    public static Tuple extract(List<Integer> l, int i) {
        // Verify arguments
        assert 0 <= i && i < l.size();

        // Extract element i
        List<Integer> sub = new ArrayList<>(l);
        Integer e = sub.remove(i);
        return new Tuple(e, sub);
    }


    /**
     * 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 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) {
        // Verify arguments
        assert l.size() == new HashSet<>(l).size();

        // Base case
        if (l.size() <= 1) {
            return List.of(l);
        }

        // Recursive call
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < l.size(); i++) {
            Tuple t = extract(l, i);
            res.addAll(appendAll(t.e, allPermutations(t.l)));
        }
        return res;
    }


    /**
     * 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 extract
        assert extract(List.of(1, 2, 3), 0).equals(new Tuple(1, List.of(2, 3)));
        assert extract(List.of(1, 2, 3), 1).equals(new Tuple(2, List.of(1, 3)));
        assert extract(List.of(1, 2, 3), 2).equals(new Tuple(3, List.of(1, 2)));
        assert extract(List.of(1), 0).equals(new Tuple(1, new ArrayList<>()));

        // 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 allPermutations
        assert allPermutations(new ArrayList<>()).equals(List.of(new ArrayList<>()));
        assert allPermutations(List.of(1)).equals(List.of(List.of(1)));
        assert allPermutations(List.of(1, 2)).equals(List.of(List.of(1, 2), List.of(2, 1)));
        assert allPermutations(List.of(1, 2, 3)).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)));
    }

}

Now, you have to adapt your function(s) in order to return only the permutations that satisfy the following condition: the sum of the first nb elements is less than or equal to a value threshold. We assume that the list only contains positive integers.

The condition must be evaluated during the construction of the permutations. In other words, it must not be applied as a post-processing step. Indeed, doing so afterward would be useless to save time as all permutations would be computed already.

Correction
​
# Needed imports
from typing import List, Tuple



def extract (l: List[int], i: int) -> Tuple[int, List[int]]:

    """
        This function extracts the value at index i from a list l.
        In:
            * l: The list from which the value at index i is to be extracted.
            * i: The index of the value to be extracted.
        Out:
            * A tuple with the value at index i and the list without the value at index i.
    """

    # Verify arguments
    assert 0 <= i < len(l)

    # Extract element i
    return l[i], l[:i] + l[i+1:]



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

    # Verify arguments
    assert len(l) == len(set(l))
    assert all(e >= 0 for e in l)

    # Inner recursive function to treat a problematic case
    def _some_permutations (l: List[int], nb: int, threshold: int) -> List[List[int]]:

        # Base case 1
        if nb >= 0 and threshold < 0:
            return []

        # Base case 2
        if len(l) <= 1:
            return [l]
        
        # Recursive call
        result = []
        for i in range(len(l)):
            e, sub = extract(l, i)
            result += append_all(e, _some_permutations(sub, nb - 1, threshold - e))
        return result
    
    # Handle problematic case and use function
    if len(l) == 1 and l[0] > threshold:
        return [[]]
    return _some_permutations(l, nb, threshold)



# Tests for extract
assert extract([1, 2, 3], 0) == (1, [2, 3])
assert extract([1, 2, 3], 1) == (2, [1, 3])
assert extract([1, 2, 3], 2) == (3, [1, 2])
assert extract([1], 0) == (1, [])

# 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 some_permutations
assert some_permutations([], 1, 2) == [[]]
assert some_permutations([1], 1, 1) == [[1]]
assert some_permutations([1], 1, 0) == [[]]
assert some_permutations([1, 2], 1, 1) == [[1, 2]]
assert some_permutations([1, 2], 1, 3) == [[1, 2], [2, 1]]
assert 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 some_permutations([1, 2, 3], 2, 4) == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [3, 1, 2]]
assert 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]]
/**
 * 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.
 */

// Needed imports
import java.util.ArrayList;
import java.util.List;
import java.util.HashSet;

public class Main {

    /**
     * Unlike Python, a Java method can only return a single value.
     * Here, using a record allows you to return a pair of values encapsulated in a single element, a Tuple.
     *
     * @see https://docs.oracle.com/en/java/javase/16/language/records.html
     */
    public record Tuple(Integer e, List<Integer> l) {
    }


    /**
     * This function extracts the value at index i from a list l.
     *
     * @param l The list from which the value at index i is to be extracted.
     * @param i The index of the value to be extracted.
     * @return A tuple with the value at index i and the list without the value at index i.
     */
    public static Tuple extract(List<Integer> l, int i) {
        // Verify arguments
        assert 0 <= i && i < l.size();

        // Extract element i
        List<Integer> sub = new ArrayList<>(l);
        Integer e = sub.remove(i);
        return new Tuple(e, sub);
    }


    /**
     * 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 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 all permutations of l.
     */
    public static List<List<Integer>> somePermutations(List<Integer> l, int nb, int threshold) {
        // Verify arguments
        assert l.size() == new HashSet<>(l).size();
        assert l.stream().allMatch(e -> e >= 0);

        // Handle problematic case and use function
        if (l.size() == 1 && l.get(0) > threshold) {
            List<List<Integer>> result = new ArrayList<>();
            result.add(new ArrayList<>());
            return result;
        }
        return _somePermutations(l, nb, threshold);
    }


    /**
     * Private recursive function to treat a problematic case.
     *
     * @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 all permutations of l.
     */
    private static List<List<Integer>> _somePermutations(List<Integer> l, int nb, int threshold) {
        // Base case 1
        if (nb >= 0 && threshold < 0) {
            return new ArrayList<>();
        }

        // Base case 2
        if (l.size() <= 1) {
            List<List<Integer>> singleResult = new ArrayList<>();
            singleResult.add(new ArrayList<>(l));
            return singleResult;
        }

        // Recursive call
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < l.size(); i++) {
            Tuple t = extract(l, i);
            result.addAll(appendAll(t.e, _somePermutations(t.l, nb - 1, threshold - t.e)));
        }
        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 extract
        assert extract(List.of(1, 2, 3), 0).equals(new Tuple(1, List.of(2, 3)));
        assert extract(List.of(1, 2, 3), 1).equals(new Tuple(2, List.of(1, 3)));
        assert extract(List.of(1, 2, 3), 2).equals(new Tuple(3, List.of(1, 2)));
        assert extract(List.of(1), 0).equals(new Tuple(1, new ArrayList<>()));

        // 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 somePermutations
        assert somePermutations(new ArrayList<>(), 1, 2).equals(List.of(new ArrayList<>()));
        assert somePermutations(List.of(1), 1, 1).equals(List.of(List.of(1)));
        assert somePermutations(List.of(1), 1, 0).equals(List.of(new ArrayList<>()));
        assert somePermutations(List.of(1, 2), 1, 1).equals(List.of(List.of(1, 2)));
        assert somePermutations(List.of(1, 2), 1, 3).equals(List.of(List.of(1, 2), List.of(2, 1)));
        assert somePermutations(List.of(1, 2, 3), 1, 3).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)));
        assert somePermutations(List.of(1, 2, 3), 2, 4).equals(List.of(List.of(1, 2, 3), List.of(1, 3, 2), List.of(2, 1, 3), List.of(3, 1, 2)));
        assert somePermutations(List.of(1, 2, 3), 3, 6).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)));
    }

}

To go further

Important

The content of this section is optional. It contains additional material for you to consolidate your understanding of the current topic.

10 — Check if a list contains an element

Write a recursive function dicho_contains(l, e) that returns true if a list l contains the integer e, false otherwise.

You must use a dichotomic approach. The dichotomic search is a search algorithm that divides the search interval in half at each step.

Again, make sure that your code is correct by running it with different inputs and checking the results.

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)
/**
 * 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.
 */

// Needed imports
import java.util.List;
import java.util.ArrayList;

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);
    }

}

If the list is ordered, we can exploit this property to improve the search efficiency.

Below is a modified version of dicho_contains relying on this property.

​
# 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)
/**
 * 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.
 */

// Needed imports
import java.util.List;
import java.util.ArrayList;

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);
    }

}

Try to answer the following questions:

  • What happens if the list given as parameter is not ordered?

    Correction

    The function assumes that l is sorted, in order to only make the recursive call on the correct half of the list at each iteration. If we break this property, there is a chance that e appears in the half that is not searched. Therefore, the function may not find it, and return false instead of the expected true.

  • Why was the base case 2 removed?

    Correction

    When we split the list in halves, we check if the midpoint contains e. Therefore, there is no use to search it again there.

    You could argue it is the same to include e in, say, the leftmost list. However, why continuing to make recursive calls up to one element left, if we directly find e when splitting the list in halves?

11 — Number of coin changes

Write a recursive function count_coin_changes(amount, coins) that counts the number of ways to reach an amount value by adding only the values that belong to the coins list. All coins are non zero natural numbers and can be used as many times as necessary. The order in which the coins are used is not significant.

For example, the number of ways to reach the value amount = 3 with coins = [1, 2] is 2 : [1, 1, 1] and [1, 2]. Here, [2, 1] is equivalent to [1, 2] and only one of the two combinations is considered.

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
/**
 * 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.
 */

// Needed imports
import java.util.List;

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;
    }

}

Now, write a recursive function list_coin_changes(amount, coins) that lists all the ways to reach an amount value by adding only the values that belong to the coins list. All coins are non zero natural numbers and can be used as many times as necessary. The order in which the coins are used is not significant.

For example, the ways to reach the value amount = 3 with coins = [1,2] are [[1, 1, 1], [1, 2]]. Here again, [2, 1] is equivalent to [1, 2] and only one of the two combinations appears.

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]]
/**
 * 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.
 */

// Needed imports
import java.util.ArrayList;
import java.util.List;

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)));
    }

}

To go beyond

Important

The content of this section is very optional. We suggest you directions to explore if you wish to go deeper in the current topic.

12 — Tail recursion

You can try to make all functions above tail recursive. Check again the article on recursion for more details on how to do it.

13 — Use AI

Now that you have done the exercises without AI tools, try to see how you could solve them faster (and possibly better) using tools such as GitHub Copilot!