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

The aim of this session is to help you master important notions in computer science. An intelligent programming assistant such as GitHub Copilot, that you may have installed already, will be able to provide you with a solution to these exercises based only on a wisely chosen file name.

For the sake of training, we advise you to disable such tools first.

At the end of the practical activity, we suggest you to work on the exercise again with these tools activated. Following these two steps will improve your skills both fundamentally and practically.

Also, 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
// 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 — 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
// 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 — 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



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

}

Now, write a function that returns 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 to filter out invalid permutations. Indeed, doing so afterward would be useless to save time as all permutations would be computed already.

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 — Optimize your solutions

What you can do now is to use AI tools such as GitHub Copilot or ChatGPT, either to generate the solution, or to improve the first solution you came up with! Try to do this for all exercises above, to see the differences with your solutions.

To go further

11 — 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)
// 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);
    }

}

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

}

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?

12 — 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
// 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;
    }

}

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

}

To go beyond

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