NSI Cours Terminale : Recursivité

Récursivité

On rappelle qu’on peut appeler des fonctions dans une autre fonction.

def salutation(nom, adjectif):
    return "Bonjour, " + nom + ". Tu es " + adjectif + "."

def affiche_salutations(nom1, nom2):
    print( salutation(nom1, "beau") )
    print( salutation(nom2, "belle") )

affiche_salutations("Jean", "Paulette")

Mais les fonctions peut également s’appeler elle-même !

Définition : Une fonction est dite récursive lorsqu’elle s’appelle elle-même.

Exemple : La fonction suivante est récursive.

def spammer():
    "Je te spamme"
    spammer()

spammer()

Évidemment, ce programme ne s’arrête pas (sans erreur).

Nous sommes tombés dans un piège qui sera systématiquement présent lors d’une programmation récursive : le piège de la boucle infinie.

La récursivité peut être en algorithmique une bonne méthode, à condition de respecter une règle cruciale : l’existence d’un CAS DE BASE.

Voilà un exemple qui se termine.

Remarquez qu’il y a un if pour le cas de base.

def nouvel_an(nombre):
    if nombre == 0: # cas de base
        print("Bonne année !")
    else:
        print(nombre)
        nouvel_an(nombre - 1)

nouvel_an(5)

Le cas de base est la condition qui permet d’arrêter la récursion.

Par exemple, dans nouvel_an, le cas de base est quand nombre égal $0$ .

On peut avoir plusiers cas de base.

L’arbre d’appels (ou arbre d’exécution) est une représentation visuelle de toutes les instances de la fonction et de leurs relations pendant l’exécution du programme.

from magie import arbre_d_appels
@arbre_d_appels
# Ignorer les lignes ci-dessus.
# Ce n'est pas pertinent pour le cours.
def nouvel_an(nombre):
    if nombre == 0:
        print("Bonne année !")
    else:
        print(nombre)
        nouvel_an(nombre - 1)

nouvel_an(5)

Nous remarquons que nouvel_an aurait pu être définie sans récursivité, mais nous utilisons cet exemple pour comprendre les fondements de la récursivité.

Exercice tous ensembles : On considère la fonction factorielle(n) notée $n!$ en mathématiques), qui calcule le produit d’un entier $n$ par les entiers positifs qui lui sont inférieurs : $n! = n\times (n-1)\times (n-2)\times\dots\times 3\times 2 \times 1.$

Exemple : $5! = 5\times 4\times 3 \times 2 \times 1 = 120$

Mais nous pouvons aussi définir la factorielle récursivement (mathématiquement parlant) :

P(n) = \begin{cases} 1 & \text{si }n = 1\\ n \times P(n-1) & \text{si }n > 1 \end{cases}

Exemple :

\begin{align*} P(5) &= 5\times P(4)\\ &= 5 \times 4\times P(3)\\ &= 5 \times 4\times 3 \times P(2)\\ &= 5 \times 4\times 3 \times 2 \times P(1)\\ &= 5 \times 4\times 3 \times 2 \times 1 = 120 \end{align*}

Programmer de manière impérative (manière classique) la fonction factorielle.
Programmer de façon récursive la fonction factorielle.

# coder ici pour la question 1

# coder ici pour la question 2

Pair ou impair?

On voudrait savoir si un entier positif est pair ou pas.

On sait que $1$ n’est pas pair et que $2$ est pair.

On sait aussi que si $x$ est pair, alors $x - 2$ est pair. De même, si $x$ est impair, alors $x - 2$ est impair.

Alors, on peut coder la fonction récursive suivante :

def est_pair(x):
    if x == 1:
        # Si x est égal à 1, la fonction renvoie False.
        return False
    if x == 2:
        # Si x est égal à 2, la fonction renvoie True.
        return True
    # Si on arrive à ce point, on exécute le code ci-dessous.
    reponse = est_pair(x-2)
    return reponse

Quand une fonction renvoie quelque chose, cela termine l’exécution.

Par exemple, si on appells est_pair(1), la fonction renvoie False et se termine.

Elle ne va pas continuer, donc elle ne va pas exécuter toutes les lignes aen-dessous, comme reponse = est_pair(x-2).

est_pair(1)

from magie import arbre_d_appels
@arbre_d_appels
# Ignorer les lignes ci-dessus.
# Ce n'est pas pertinent pour le cours.
def est_pair(x):
    if x == 1:
        # Si x est égal à 1, la fonction renvoie False.
        return False
    if x == 2:
        # Si x est égal à 2, la fonction renvoie True.
        return True
    # Si on arrive à ce point, on exécute le code ci-dessous.
    reponse = est_pair(x-2)
    return reponse

est_pair(9)

est_pair(6)

Bien sûr, on peut implémenter une telle fonction plus simplement, mais c’est important de faire un exemple assez simple pédagogiquement.

Exemple : Fibonacci

La suite de Fibonacci est définie comme :

F(n) = \begin{cases} 1 & \text{si }n = 1 \text{ ou }n = 2, \\ F(n-1) + F(n-2) & \text{si }n > 2, \\ \end{cases}

Les premiers termes de cette suite sont : $1,1,2,3,5,8,13,21,34...$

Voici une implémentation de la suite de Fibonacci.

def fibo(n):
    if n == 1 or n == 2:
        return 1
    return fibo(n-1) + fibo(n-2)

fibo(3)

fibo(7)

fibo(27)

fibo(35)

On peut afficher l’arbre d’appels.

from magie import arbre_d_appels
@arbre_d_appels
# Ignorer les lignes ci-dessous.
# Ce ne sont pas pertinents pour le cours.
def fibo(n):
    if n == 1 or n == 2:
        return 1
    return fibo(n-1) + fibo(n-2)

fibo(6)

On peut remarquer (par exemple) que fibo(2) est calculé 5 fois…

Des valeurs sont calculés plusieurs fois, c’est pour ça que fibo(35) met du temps à s’exécuter. C’est un des principales inconvénients de la récursivité.

Nous verrons plus tard comment contourner ce problème dans une prochaine leçon. (à suivre…)

Exercices

Une fonction `mystere`

On considère la fonction mystere suivante :

def mystere(x, n):
    """ x de type float
        n entier naturel """
    if n == 1:
        return x
    else:
        return x * mystere(x, n-1)

(a) Que renvoient les appels suivants (essayer de trouver avant d’exécuter) :

mystere(4,2)
mystere(2,6)
mystere(101, 1)

(b) Dessiner l’arbre d’appel de mystere(5,3).

Somme des premiers entiers

La somme des $n$ premiers entiers peut être exprimer comme une fonction récursive :

S(n) = \begin{cases} 1&\text{ si }n=1\\ S(n-1) + n&\text{ si }n \geq 1 \end{cases}

par exemple $S(3)= 1+2+3=6$ et $S(5)=1+2+3+4+5=15$ .

(a) Qu’est-ce qui ne va pas dans l’implémentation suivante ?

(b) Corrigez l’erreur.

def somme_jusqua(n):
    return somme_jusqua(n-1) + n

somme_jusqua(5)

Que renvoie `f` ?

On considère la fonction f suivante qui prend comme argument n un entier positif :

def f(n):
    if n == 0:
        return 0
    else:
        return f(n - 2)

(a) Que renvoie l’appel f(6) ?

(b) L’appel f(n) se termine-t-il pour toutes les valeurs de n ?

(c) Recopier et ajouter des lignes de code à la fonction f pour que f(n) renvoie 0 si n est un entier naturel pair et 1 si n est un entier naturel impair.

# Recopier la fonction ici.

(d) Que se passe-t-il si l’appel f(-1) est effectué ? Proposer une solution à ce problème.

`disparaitre_lentement`

Pour cet exercice, on parle de la fonction disparaitre_lentement qui prend comme argument une chaîne de caractères s.

Elle affiche s, enleve son premier caractère, affiche s de nouveau, etc.

Elle termine quand la chaîne de caractères est vide.

Par exemple, si s = adieu:

print("adieu")
print("dieu")
print("ieu")
print("eu")
print("u")

Écrivez la fonction disparaitre_lentement qui prend comme argument une chaine s.

# Ecrivez la fonction ici.

disparaitre_lentement("Je t'aime !")
# Je t'aime!
# e t'aime!
#  t'aime!
# t'aime!
# 'aime!
# aime!
# ime!
# me!
# e!
# !

Dessinez l’arbre d’appels pour disparaitre_lentement('Ciao!').

`recherche_rec`

Complétez la fonction recherche_rec récursive qui prend comme argument une liste liste d’entiers et un entier cible.

Elle renvoie True si cible se trouve dans liste et False sinon.

Testez sur des exemples.

def recherche_rec(liste, cible):
    if len(liste) == 0:
        ❓❓❓
    premier_element = liste[0]
    le_reste_de_la_liste = liste[1:]
    # Si le premier_element de la liste est égal à cible...
    # ... cible se trouve dans liste
    # Alors on renvoie True.
    if ❓❓❓
        return True
    # Si cible se trouve dans le_reste_de_la_liste...
    # ... cible se trouve dans liste
    # Alors on renvoie True.
    return recherche_rec(le_reste_de_la_liste, cible)

liste_exemple = [1, 30, 34, 41, 42, 57, 66, 73, 84]
recherche_rec(liste_exemple, 70)

liste_exemple = [1, 30, 34, 41, 42, 57, 66, 73, 84]
recherche_rec(liste_exemple, 57)

Le triangle de Pascal est une présentation des coefficients binomiaux sous la forme d’un triangle défini ainsi de manière récursive :

C(n,p)=\left\{ \begin{aligned} 1\qquad\qquad\qquad\qquad\qquad\quad&\text{si}\;p=0\;\text{ou}\;n=p,\\ C(n-1,p-1)+C(n-1,p)\quad&\text{sinon}. \end{aligned}\right.

Écrivez une fonction récursive C(n, p) qui renvoie la valeur de $C(n,p)$ .
Dessinez l’arbre d’appels pour C(5, 2).

Pourquoi ?

On peut écrire des relations de cause à effet en utilisant des dictionnaires Python.

On pourrait définir les clés comme les effets et les valeurs comme les causes. Par exemple :

pourquoi = {
    "J'ai raté mon examen de NSI.": "Je n'ai pas assez étudier.",
    "Je n'ai pas assez étudier.": "J'étais trop fatigué.",
    "J'étais trop fatigué.": "J'ai trop fait la fête.",
    "J'ai réussi mon examen de NSI.": "J'ai bossé toute la semaine.",
    "J'ai vomi.": "J'ai trop fait la fête.",
    "Je ne suis pas allé en classe.": "J'ai vomi.",
    "J'ai bossé toute la semaine.": "Je veux réussir dans la vie.",
    "Je doit fournir un certificat medical.": "Je ne suis pas allé en classe."
}

pourquoi["J'ai raté mon examen de NSI."]

pourquoi["Je n'ai pas assez étudier."]

pourquoi["J'étais trop fatigué."]

pourquoi["J'ai reussi mon examen de NSI."]

Écrivez la fonction cause_racine qui prend comme argument telle dictionnaire dico, et une chaîne de caractères effet.

Si la chaîne de caractères effet n’est pas une clé du dictionnaire, la fonction renvoie la chaîne de caractères effet.
Si la chaîne de caractères effet est une clé du dictionnaire, la fonction appelle cause_racine avec dico et dico[effet] comme arguments.

# Écrivez la fonction ici.

Voici quelques exemples pour vous aider.

cause_racine(pourquoi, "J'ai raté mon examen de NSI.")
# "J'ai trop fait la fête."

cause_racine(pourquoi, "Je doit fournir un certificat medical.")
# "J'ai trop fait la fête."

cause_racine(pourquoi, "J'ai réussi mon examen de NSI.")
# 'Je veux réussir dans la vie.'

cause_racine(pourquoi, "Je suis si beau.")
# "Je suis si beau."

Est-ce que cause_racine est une fonction récursive ? Justifiez votre réponse.

Factorielle décroissante

La fonction factorielle décroissante, notée $d(x, n)$ , est définie comme le produit de $n$ entiers décroissants à partir de $x$ . Formellement, pour $n > 0$ :

d(x, n) = x \times (x - 1) \times (x - 2) \times \ldots \times (x - n + 1)

Par exemple, $d(11,4) = 11 \times 10 \times 9 \times 8 = 7920$ .

Par convention, si $n = 0$ , on définit $d(x, n) = 1$ .

Écrivez une fonction récursive factorielle_decroissante(x, n) qui prend comme argument deux entiers x et n strictement positifs.

Elle renvoie $d(x, n)$ .

factorielle_decroissante(11, 4) # 7920

Palindrome

Un palindrome est une chaîne de caractères qui reste identique même si on la renverse. Par exemple, kayak est un palindrome.

Parmi les chaînes de caractères suviantes, lesquelles sont des palindromes ?

palindome
aa
11
B
69
anna
hannah
bannad
xabcx
arelevermonnommonnomrevelera
())(
()()

Exercices (Partie A)

Vrai ou faux ? Si c’est faux, fournissez un contre-exemple.

Une chaîne de caractères contenant une seule lettre est un palindrome.
Une chaîne de caractères vide est un palindrome.

Exercices (Partie B)

Supposons que s soit une chaîne de caractères de longueur au moins égale à 2.

Supposons que car_prem est le premier caractère de s et que car_der est le dernier caractère de s.

Supposons que t soit exactement s mais avec le premier et le dernier caractères retirés.

Vrai ou faux ? Si c’est faux, fournissez un contre-exemple.

Si car_prem et car_der sont égaux, alors $s$ est un palindrome.
Si $t$ est un palindrome, alors $s$ est un palindrome.
Si car_prem et car_der sont égaux et que $t$ est un palindrome, alors $s$ est un palindrome.”

Exercice pratique

Écrivez la fonction récursive est_palindrome qui prend comme argument une chaîne de caractères s et qui renvoie True si s est un palindrome et False sinon.

print(est_palindrome('arelevermonnommonnomrevelera')) # True
print(est_palindrome('()()')) # False

Combien de façons ?

Écrivez une fonction récursive combien_de_facons qui prend comme arguments deux entiers positifs x et y et renvoie le nombre de façons d’aller de $(0,0)$ à un point $(x, y)$ si l’on peut uniquement monter (augmenter l’ordonnée $y$ de 1) ou aller à droite (augmenter l’abscisse $x$ de 1).

Si $(x, y) = (0, 0)$ , la fonction renvoie 1.

combien_de_facons(2, 1) # 3

combien_de_facons(2, 3) # 10

combien_de_facons(5, 7) # 792

combien_de_facons(3, 20) # 1771

# Ça peut prendre quelques temps.
combien_de_facons(12, 12) # 2704156

Recopiez et modifiez votre fonction récursive combien_de_facons.

Maintenant, en plus de x et y, la fonction doit également prendre un argument optionnel obstacles, qui est une liste de tuples $(a, b)$ .

Sa valeur par défaut serait la liste vide.

La fonction combien_de_facons doit renvoyer combien de façons il y a d’aller à $(x, y)$ sans passer par aucun des obstacles dans la liste.

combien_de_facons(2, 3, [(1, 1)]) # 4

combien_de_facons(5, 7) # 792

combien_de_facons(5, 7, [(3, 4)]) # 442

combien_de_facons(5, 7, [(0, 1), (1, 0)]) # 0

combien_de_facons(5, 7, [(0, 0)]) # 0

combien_de_facons(12, 12, [(1, 5), (9, 10)]) # 1666652

Recopiez et modifiez votre fonction récursive combien_de_facons.

Maintenant, en plus de x, y et obstacles, la fonction doit également prendre un argument optionnel directions, qui est une liste de tuples $(s, t)$ .

Sa valeur par défaut serait la liste [(0, 1), (1, 0)].

(0, 1) représente qu’on peut se déplacer de $1$ étape vers le haut,
(1, 0) représente qu’on peut se déplacer de $1$ étape vers la droite,

En général, si la direction $(s, t)$ est dans la liste, cela signifie qu’on peut se déplacer à la position $(x + s, y + t)$ si on est à $(x, y)$ et qu’il n’y a aucun obstacle à $(x + s, y + t)$ .

On suppose que les valeurs de $s$ et $t$ pour chaque élément de la liste sont des entiers positifs, et que $(0, 0)$ n’est pas dans la liste.

La fonction combien_de_facons devra renvoyer combien de façons il y a d’aller à (x, y) sans passer par aucun des obstacles dans la liste en se déplaçant uniquement selon

combien_de_facons(2, 3, obstacles=[(1, 1)]) # 4

combien_de_facons(4, 6, directions=[(5, 5)]) # 0

combien_de_facons(4, 6, [(2, 3)], [(2, 3)]) # 0

combien_de_facons(4, 6, [(1, 1), (0, 1), (1, 0)], [(2, 3)]) # 1

combien_de_facons(9, 6, directions=[(1, 2), (2, 1)]) # 5

combien_de_facons(9, 6, directions=[(1, 0), (0, 1), (1, 2), (2, 1)]) # 47682

combien_de_facons(9, 6, directions=[(1, 0), (0, 1), (1, 2), (2, 1)], obstacles=[(3, 3), (0, 1), (1, 0)]) # 5108

Ce cours a été écrit grâce à une collaboration entre Pierre Brun, professeur de mathématiques et moi, Jared Asuncion. Il s'agit d'un cours de spécialité NSI pour des terminales générales.

Elles ont été initialement rédigées sous forme de notebooks Jupyter, mais nous les avons converties en HTML pour une meilleure lisibilité dans les browsers.

C'est un travail en cours de réalisation. N'hésitez pas à nous contacter à l'adresse mail nsi arobase guissmo point com pour tout commentaires, questions ou suggestions.

«NSI Cours Terminale : Rappel (4ème partie)All posts on NSI|

«NSI Cours Terminale : Rappel (4ème partie)Swap Pocket out with Omnivore on your Kobo»

GUISSMO

GUISSMO

NSI Cours Terminale : Recursivité

Récursivité

Pair ou impair?

Exemple : Fibonacci

Exercices

Une fonction `mystere`

Somme des premiers entiers

Que renvoie `f` ?

`disparaitre_lentement`

`recherche_rec`

Pourquoi ?

Factorielle décroissante

Palindrome

Exercices (Partie A)

Exercices (Partie B)

Exercice pratique

Combien de façons ?

GUISSMO

GUISSMO

NSI Cours Terminale : Recursivité

Récursivité

Pair ou impair?

Exemple : Fibonacci

Exercices

Une fonction mystere

Somme des premiers entiers

Que renvoie f ?

disparaitre_lentement

recherche_rec

Pourquoi ?

Factorielle décroissante

Palindrome

Exercices (Partie A)

Exercices (Partie B)

Exercice pratique

Combien de façons ?

Une fonction `mystere`

Que renvoie `f` ?

`disparaitre_lentement`

`recherche_rec`