Summary  
This chapter covers recursion, detailing how to define a base case and a recursive case so a function calls itself with simpler inputs, and explains how the call stack manages these nested calls.  

General domain of usage  
Processing tree data structures

Une **fonction récursive** est une fonction qui s'appelle elle-même pour résoudre un problème en le divisant en parties plus petites et plus simples.



Définition

Les éléments clés de la récursion sont :
- **Cas de base** : la condition qui arrête la récursion ;
- **Cas récursif** : la partie où la fonction s'appelle elle-même avec une entrée plus simple.

## Pourquoi utiliser la récursion ?

Certains problèmes peuvent être naturellement exprimés en termes de sous-problèmes plus petits. La récursion offre une manière claire et élégante de les résoudre en permettant à une fonction de s'appeler elle-même pour traiter les cas plus simples. Elle est couramment utilisée pour des tâches telles que le traitement d'arbres, l'exploration de chemins ou la décomposition de structures (par exemple, listes, chaînes de caractères).



def print_message(message, times):
    if times > 0:                              # Base case: stop when times is 0
        print(message)
        print_message(message, times - 1)     # Recursive case

print_message("Hello, Recursion!", 3)

Procéder étape par étape pour comprendre le fonctionnement :

1. `times = 3` → condition vraie, affichage du message, appel de `print_message(message, 2)` ;
2. `times = 2` → condition vraie, affichage du message, appel de `print_message(message, 1)` ;
3. `times = 1` → condition vraie, affichage du message, appel de `print_message(message, 0)` ;
4. `times = 0` → condition fausse, la récursivité s'arrête.

**Résultat** : le message est affiché trois fois.



## La pile d'appels

Chaque fois que la fonction s'appelle elle-même, elle ajoute une nouvelle trame à la **pile d'appels** — une structure mémoire qui garde la trace des appels de fonctions actifs. Une fois le cas de base atteint, chaque appel précédent se termine un par un dans l'ordre inverse.

Toute fonction récursive doit comporter un cas de base. Sans cela, la fonction s'appellera indéfiniment et provoquera une `RecursionError`.

Remarque

import unittest

def _dynamic_test(test_case, condition, success_message, failure_message):
    if condition:
        test_case._testMethodName = success_message
        test_case.assertTrue(True, success_message)
    else:
        test_case._testMethodName = failure_message
        test_case.fail(failure_message)

class TestListSum(unittest.TestCase):

    def test_list_sum_basic(self):
        import user_code
        try:
            result = user_code.list_sum([1, 2, 3, 4, 5])
            expected = 15
            condition = result == expected
            failure_message = f"Expected `{expected}` for `[1, 2, 3, 4, 5]`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, f"The `list_sum` returns `15` for `[1, 2, 3, 4, 5]`.", failure_message)

    def test_list_sum_another_list(self):
        import user_code
        try:
            result = user_code.list_sum([10, 20, 30])
            expected = 60
            condition = result == expected
            failure_message = f"Expected `{expected}` for `[10, 20, 30]`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, f"The `list_sum` returns `60` for `[10, 20, 30]`.", failure_message)

    def test_list_sum_empty(self):
        import user_code
        try:
            result = user_code.list_sum([])
            expected = 0
            condition = result == expected
            failure_message = f"Expected `{expected}` for an empty list, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, "The `list_sum` correctly returns `0` for an empty list.", failure_message)

    def test_recursion_used(self):
        import user_code
        import inspect
        try:
            source = inspect.getsource(user_code.list_sum)
            condition = "list_sum(" in source.split("def list_sum")[1]
            failure_message = "Expected `list_sum` to call itself recursively."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, "The `list_sum` function uses recursion.", failure_message)

if __name__ == '__main__':
    unittest.main()

test_main.py

Acquérir une compréhension solide de l'influence des fonctions sur la programmation Python. Maîtriser la définition et l'appel de fonctions, la gestion des arguments, le traitement des valeurs de retour et la création de code flexible et efficace à l'aide de la récursivité et des expressions lambda.

Découvrez ce que sont les fonctions et pourquoi elles sont essentielles en Python. Apprenez à créer des fonctions, à définir des arguments, à gérer les valeurs de retour et à utiliser efficacement les fonctions intégrées.

Apprenez comment fonctionnent les arguments positionnels et optionnels en Python. Concevez des fonctions adaptables capables de gérer différents types d’entrées et d’améliorer la flexibilité de votre code.

Comprendre comment utiliser les arguments arbitraires et les arguments nommés pour gérer des tailles d'entrée variables. Apprendre comment ces techniques rendent vos fonctions plus dynamiques et organisées.

Découvrez comment les valeurs de retour représentent la sortie d'une fonction. Apprenez à retourner une ou plusieurs valeurs, à utiliser None, et explorez les générateurs pour un contrôle plus avancé du flux de données.

Découvrez des concepts avancés de fonctions avec la récursivité et les fonctions lambda. Apprenez comment la récursivité permet de résoudre des problèmes répétitifs et comment les expressions lambda créent des fonctions concises en une seule ligne.

Récursivité

Pourquoi utiliser la récursion ?

Un exemple simple

La pile d'appels

Solution