Recursive algorithms

Reading time5 min

En bref

Résumé de l’article

Dans cet article, nous vous présentons ce qu’est un algorithme récursif. En particulier, nous étudions le cas de la fonction factorielle, et montrons comment l’écrire de manière récursive. Nous montrons ensuite ce qui se passe dans la pile d’appels lors de l’exécution de cette fonction.

Points clés

  • Les fonctions récursives sont des fonctions qui s’appellent elles-mêmes.

  • Elles consistent en un cas de base et un appel récursif.

  • Elles sont généralement plus simples et plus élégantes, mais peuvent nécessiter un petit coût computationnel supplémentaire.

  • Certaines structures de données peuvent également être définies récursivement.

Contenu de l’article

1 — Qu’est-ce que la récursivité ?

La récursivité est un concept fondamental en programmation informatique qui se produit lorsqu’une fonction s’appelle elle-même directement ou indirectement. Une structure de données peut également être définie récursivement.

Une fonction récursive se compose de deux éléments principaux :

  • Le cas de base – C’est la condition qui met fin à la récursion. Sans cas de base, la fonction s’appellerait indéfiniment, ce qui entraînerait une erreur de dépassement de pile (stack overflow). Notez que le cas de base n’est pas nécessairement unique.

  • L’appel récursif – C’est lorsque la fonction s’appelle elle-même avec un ensemble modifié de paramètres, rapprochant le calcul du cas de base.

2 — Un exemple rapide

Un exemple classique de récursion est le calcul de la factorielle d’un nombre. La factorielle de $n$ (notée $n!$) est le produit de tous les entiers positifs inférieurs ou égaux à $n$ :

$$\begin{align*} n! &= \underbrace{1}_{1!} \times 2 \times \dots \times (n-1) \times n\\ n! &= \underbrace{1 \times 2}_{2!} \times \dots \times (n-1) \times n\\ n! &= \underbrace{1 \times 2 \times 3}_{3!} \times \dots \times (n-1) \times n\\ &\dots\\ n! &= \underbrace{1 \times 2 \times 3\times \dots \times (n-1)}_{(n-1)!} \times n\\ n! &= (n-1)! \times n\\ \end{align*}$$

Ce qui peut se formaliser ainsi :

$$\begin{align*} n! &= \begin{cases} 1 & \text{si $n=1$}.\\ n\times (n-1)! & \text{si $n>0$}. \end{cases} \end{align*}$$

Cette dernière formulation met en perspective la relation récursive entre $n!$ et $(n-1)!$ ainsi que le cas de base :

  • Cas de base – Lorsque $n=1$, la fonction retourne $1$. La formule mathématique de la factorielle étend la définition à $0! = 1$.

  • Appel récursif – Pour le reste, on a $n! = n\times (n-1)!$.

En termes de code, cela se traduit directement comme suit :

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

    # Base case that determines when to stop
    if n == 0:
        return 1
    
    # Recursive call that determines how to continue
    return n * factorial(n - 1)



# Don't forget to test your function
assert factorial(0) == 1
assert factorial(1) == 1
assert factorial(5) == 120
/**
 * 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) {
        // Base case that determines when to stop
        if (n == 0) {
            return 1;
        }

        // Recursive call that determines how to continue
        return n * factorial(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 factorial(0) == 1;
        assert factorial(1) == 1;
        assert factorial(5) == 120;
    }

}
Information

Dans le cas de la factorielle, le résultat est garanti uniquement pour les nombres positifs. C’est la responsabilité du développeur de s’assurer de la bonne utilisation de son code. Par exemple, la documentation de cette fonction devrait mentionner comment elle gère les nombres négatifs.

Vous pouvez également utiliser des assertions pour transformer votre code comme suit :

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

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

    # Base case that determines when to stop
    if n == 0:
        return 1
    
    # Recursive call that determines how to continue
    return n * factorial(n - 1)



# Don't forget to test your function
assert factorial(0) == 1
assert factorial(1) == 1
assert factorial(5) == 120
/**
 * 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) {
        // Make sure that n has a correct value
        assert n >= 0;

        // Base case that determines when to stop
        if (n == 0) {
            return 1;
        }

        // Recursive call that determines how to continue
        return n * factorial(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 factorial(0) == 1;
        assert factorial(1) == 1;
        assert factorial(5) == 120;
    }
}

3 — Avantages et inconvénients

Les principaux avantages de l’utilisation de la récursivité sont que les fonctions récursives sont la plupart du temps plus claires, plus simples, plus courtes et plus faciles à comprendre que leurs équivalents non récursifs.

La récursivité repose sur l’appel répété de la même fonction. Un appel de fonction récursive est souvent plus coûteux qu’une boucle (c’est-à-dire sa version non récursive). Ainsi, les surcoûts associés à un appel de fonction récursive sont :

  • Espace – Un appel de fonction nécessite de l’espace pour les paramètres et les variables locales, ainsi qu’une indication de l’endroit où retourner. Cet espace est alloué sur la “pile” et libéré lorsque la fonction retourne. Un algorithme récursif peut nécessiter un espace proportionnel au nombre d’appels imbriqués.

  • Temps – Appeler une fonction prend du temps car cela alloue et libère de la mémoire locale, copie des valeurs dedans, etc.

4 — La pile d’appels

La récursivité dans l’exécution d’un programme implique plusieurs étapes clés, notamment la gestion des appels de fonctions, la création de nouvelles instances de fonctions et la gestion de la pile d’appels.

Voici une illustration de l’utilisation de la pile lors de l’appel factorial(3) :

Pour aller plus loin

5 — Récursion terminale

Dans la récursion traditionnelle (exemple ci-dessus), vous effectuez d’abord les appels récursifs puis utilisez leurs résultats intermédiaires pour calculer le résultat final.

Ce processus peut être modifié pour :

  • D’abord – calculer le résultat intermédiaire.

  • Puis – le passer en argument à l’appel récursif. L’appel récursif est retourné tel quel, c’est-à-dire sans opérations a posteriori.

Cette façon de faire s’appelle la récursion terminale. Certains compilateurs intelligents peuvent reconnaître cette forme de récursion et la transformer en boucles (exécutées en “espace constant”).

Information

Rappelez-vous que le but de cette leçon est de comprendre la récursivité afin que vous puissiez développer des méthodes récursives simples et correctes, indépendamment de leur efficacité.

Pour mémoire, voici la manière de coder la fonction factorielle en récursion terminale :

​
def factorial_tail (n: int, tmp_result: int = 1) -> 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.
            * tmp_result: The current result of the factorial calculation.
        Out:
            * The factorial of n.
    """

    # Base case that determines when to stop
    if n == 0:
        return tmp_result

    # Recursive call that determines how to continue
    return factorial_tail(n - 1, n * tmp_result)



# Don't forget to test your function
assert factorial_tail(0) == 1
assert factorial_tail(1) == 1
assert factorial_tail(5) == 120
/**
 * 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.
     * @param tmpResult The current result of the factorial calculation.
     * @return The factorial of n.
     */
    public static int factorialTail(int n, int tmpResult) {
        // Base case that determines when to stop
        if (n == 0) {

            return tmpResult;
        }

        // Recursive call that determines how to continue
        return factorialTail(n - 1, n * tmpResult);
    }


    /**
     * 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 factorialTail(0, 1) == 1;
        assert factorialTail(1, 1) == 1;
        assert factorialTail(5, 1) == 120;
    }

}

La méthode attend deux arguments : n et la valeur initiale de tmp_result. Étant donné l’opération d’accumulation (*), le second paramètre doit être fixé à 1 lors de l’appel initial.

Voici une illustration de l’utilisation de la pile lors de l’appel factorial_tail(3, 1) :

Information

Il faut noter qu’aucun calcul n’est appliqué à la valeur de retour. Le résultat final, 6, n’est pas modifié une fois qu’il a été calculé.

6 — Structures de données récursives

Bien que nous n’entrerons pas dans les détails ici, la récursivité peut également apparaître dans les structures de données.

Un exemple courant est la liste chaînée. Une liste chaînée est une structure de données où les éléments sont stockés dans des emplacements séparés et liés entre eux à l’aide de références. Chaque nœud a deux parties :

  • Données – L’élément à stocker dans le nœud.
  • Lien – Une référence vers le nœud suivant.

Dans une liste chaînée, le dernier nœud a généralement une référence qui est définie à None (ou null en Java), indiquant qu’il n’y a pas d’autres nœuds dans la séquence. Cette structure est efficace pour insérer et supprimer des éléments car elle ne nécessite pas d’adapter la taille ou de décaler les éléments, comme dans un tableau.

Un arbre binaire peut également être représenté par des nœuds composés de quatre parties :

  • Données – L’élément à stocker dans le nœud.
  • Lien vers le parent – Une référence vers le nœud parent.
  • Lien vers l’enfant gauche – Une référence vers le nœud enfant gauche.
  • Lien vers l’enfant droit – Une référence vers le nœud enfant droit.

Le parent du nœud racine est null, tout comme les nœuds enfants des feuilles. Le parcours d’un arbre représenté de cette manière est simple à exprimer à l’aide d’une fonction récursive.

Pour aller plus loin