D'après 2023, sujet zéro B Auteurs : Franck Chambon, Sébastien Hoarau

Fonctions récursives⚓︎

D'après 2023, Sujet 0.b, Ex. 2

Cet exercice est consacré à l'analyse et à l'écriture de programmes récursifs.

1.a) Expliquer en quelques mots ce qu'est une fonction récursive.

1.b) On considère la fonction Python suivante :

🐍 Script Python

def compte_rebours(n):
    """ n est un entier positif ou nul """
    if n >= 0:
        print(n)
        compte_rebours(n - 1)

L'appel compte_rebours(3) affiche successivement les nombres 3, 2, 1 et 0. Expliquer pourquoi le programme s'arrête après l'affichage du nombre 0.

2. En mathématiques, la factorielle d'un entier naturel \(n\) est le produit des nombres entiers strictement positifs inférieurs ou égaux à \(n\). Par convention, la factorielle de \(0\) est \(1\). Par exemple :

la factorielle de \(1\) est \(1\)
la factorielle de \(2\) est \(2 × 1 = 2\)
la factorielle de \(3\) est \(3 × 2 × 1 = 6\)
la factorielle de \(4\) est \(4 × 3 × 2 × 1 = 24\)

Recopier et compléter sur votre copie le programme donné ci-dessous afin que la fonction récursive fact renvoie la factorielle de l'entier passé en paramètre de cette fonction.

Exemple : fact(4) renvoie 24.

🐍 Script Python

def fact(n):
    """ Renvoie le produit des entiers strictement positifs
         et inférieurs ou égaux à n.
    """
    if n == 0:
        return ...  # À compléter
    else:
        return ...  # À compléter

3. La fonction somme_entiers_rec ci-dessous permet de calculer la somme des entiers, de 0 à l'entier naturel n passé en paramètre.

Par exemple :

Pour n = 0, la fonction renvoie la valeur 0.
Pour n = 1, la fonction renvoie la valeur 0 + 1 = 1.
...
Pour n = 4, la fonction renvoie la valeur 0 + 1 + 2 + 3 + 4 = 10.

🐍 Script Python
def somme_entiers_rec(n):
    """ Renvoie, de manière récursive,
     la somme des entiers de 0 à l'entier naturel n.
    """
    if n == 0:
        return 0
    else:
        print(n)  # pour vérification
        return n + somme_entiers(n - 1)

L'instruction print(n) de la ligne 7 dans le code précédent a été insérée afin de mettre en évidence le mécanisme en œuvre au niveau des appels récursifs.

3.a) Écrire ce qui sera affiché dans la console après l'exécution de la ligne suivante :

🐍 Console Python

>>> res = somme_entiers_rec(3)

3.b) Quelle valeur sera alors affectée à la variable res ?

4. Écrire en Python une fonction somme_entiers non récursive : cette fonction devra prendre en argument un entier naturel n et renvoyer la somme des entiers de 0 à n compris. Elle devra donc renvoyer le même résultat que la fonction somme_entiers_rec définie à la question 3.

Exemple : somme_entiers(4) renvoie 10.