Récursivité Enveloppée

Autour de la suite de Fibonacci

Publié le February 25, 2021 | 13 minutes | 2563 mots |

Rappel : récursivité terminale

La définition de la fonction factorielle est $$ n! = \begin{cases} 1 & \text{if } n = 0 \cr n \times (n-1)! & \text{sinon} \end{cases} $$

Définir la fonction fact_env qui calcule la factorielle d’un entier naturel $n$, sans oublier le jeu de tests.
La spécification de la fonction est :

1
2
3
4
5
6


def fact_env(n: int) -> int:
    """
    Retourne la factorielle de n.

    Algorithme : récursivité enveloppée
    """

Réponse

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def fact_env(n: int) -> int:
    """
    Retourne la factorielle de n.

    Algorithme : récursivité enveloppée
    """
    if n == 0:
        return 1

    return n * fact_env(n - 1)


if __name__ == "__main__":
    assert fact_env(0) == 1
    assert fact_env(1) == 1
    assert fact_env(5) == 120
    assert fact_env(8) == 40320

En informatique, la récursion terminale, aussi appelée, récursion finale, est un cas particulier de récursivité assimilée à une itération.
Une fonction à récursivité terminale (dite tail-recursive en anglais) est une fonction où l’appel récursif est la dernière instruction à être évaluée. Cette instruction est alors nécessairement « pure », c’est-à-dire qu’elle consiste en un simple appel à la fonction, et jamais à un calcul ou une composition.
Les algorithmes récursifs exprimés à l’aide de fonctions à récursion terminale profitent donc d’une optimisation de la pile d’exécution.
Cette réorganisation économise de l’espace mémoire car aucun état, sauf l’adresse de la fonction appelante, n’a besoin d’être sauvé sur la pile d’exécution. Cela signifie également que le programmeur n’a pas à craindre l’épuisement de l’espace de pile ou du tas pour des récursions très profondes.

[Lire]