Algorithmes récursifs, fonctions récursives (Bac 🎯)⚓︎

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

le cours d'Olivier Lécluse
le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
la ressource Eduscol sur la récursivité
le cour e-nsi sur la récursivité
le cours de mon collègue Pierre Duclosson

🔖 Synthèse de ce qu'il faut retenir pour le bac

Algorithme d'Euclide⚓︎

Exemple 1

L'algorithme d'Euclide pour déterminer le Plus Grand Commun Diviseur de deux entiers naturels est l'un des plus anciens algorithmes connus.

Si on note PGCD(a, b) le PGCD des entiers naturels a et b et a % b le reste de la division euclidienne de a par b, alors la propriété fondamentale utilisée dans l'algorithme est que PGCD(a, b) = PGCD(b, a %b).

Déroulons l'algorithme dans le calcul de PGCD(100, 45).

Dans une première phase, dite de descente, on réduit chaque problème de calcul de PGCD à un problème de calcul de PGCD avec des entiers plus petits, jusqu'à ce qu'on atteigne un cas de base où la solution est immédiate car l'un des entiers divise l'autre.

Problème 1 à résoudre a = 100 et b = 45 et a % b = 10 donc PGCD(100, 45) = PGCD(45, 10), on se ramène au calcul de PGCD(45, 10)
Problème 2 à résoudre a = 45 et b = 10 et a % b = 5 donc PGCD(45, 10) = PGCD(10, 5), on se ramène au calcul de PGCD(10, 5)
Problème 3 à résoudre a = 10 et b = 5 et a % b = 0 donc PGCD(10, 5) = PGCD(5, 0), on se ramène au calcul de PGCD(5, 0)
Problème 4 à résoudre a = 5 et b = 0 donc a divise b donc PGCD(5, 0) = 5 c'est le cas de base

Ensuite, vient la phase de remontée de la réponse, du cas de base vers le problème initial :

Problème 4 résolu PGCD(5, 0) = 5
donc Problème 3 résolu car PGCD(10, 5) = PGCD(5, 0) donc PGCD(10, 5) = 5
donc Problème 2 résolu car PGCD(45, 10) = PGCD(10, 5) donc PGCD(45, 10) = 5
donc Problème 1 résolu car PGCD(100, 45) = PGCD(45, 10) donc PGCD(100, 45) = 5

récursif versus itératif

On donne ci-dessous deux implémentations en Python du calcul de PGCD avec l'algorithme d'Euclide.

pgcd_iteratif est une implémentation itérative c'est-à-dire avec une boucle qui permet de répéter les réductions successives du problème.

pgcd_recursif est une implémentation récursive c'est-à-dire que la fonction s'appelle elle-même pour réduire le problème à un problème similaire mais sur des entiers plus petits.

💡 Pour répéter un traitement on disposait déjà de la boucle (programme itératif), on introduit ici l'appel d'une fonction par elle-même (programme récursif).

À vous de testerRésultat

Exécutez le script puis dans la console évaluez :

pgcd_iteratif(100, 45)
pgcd_recursif(100, 45)
pgcd_recursif = trace(pgcd_recursif) puis à nouveau pgcd_recursif(100, 45) pour afficher une trace ¹ de l'éxécution de pgcd_recursif(100, 45)

🐍 Script Python

>>> pgcd_iteratif(100, 45)
>>> pgcd_recursif(100, 45)
5
>>> pgcd_recursif = trace(pgcd_recursif)
>>> pgcd_recursif(100, 45)
┌Appel de recursion_wrapper(100) => descente
| ┌Appel de recursion_wrapper(45) => descente
| | ┌Appel de recursion_wrapper(10) => descente
| | | ┌Appel de recursion_wrapper(5) => descente
| | | └Fin de recursion_wrapper(5) <= remontée
| | └Fin de recursion_wrapper(10) <= remontée
| └Fin de recursion_wrapper(45) <= remontée
└Fin de recursion_wrapper(100) <= remontée
5

Évaluations restantes : ∞/∞

Définition d'une fonction récursive⚓︎

Point de cours 1

Un algorithme récursif est un algorithme qui résout un problème en se ramenant à la résolution de un ou plusieurs sous-problèmes similaires mais plus petits jusqu'à la résolution d'un cas de base dont la réponse est directe.

On distingue deux parties dans un algorithme récursif :

la réduction consiste à réduire la résolution du problème initial de taille \(n\) à celle de un ou plusieurs sous-problèmes de même type et de taille inférieure (\(n-1\) ou \(n/2\) etc ...) : l'algorithme s'appelle alors lui-même sur ces sous-problèmes : on parle d'appels récursifs.
la résolution directe pour un cas de base

Un algorithme récursif est implémenté sous la forme d'une fonction récursive.

💡Une fonction récursive est une fonction qui s'appelle elle-même.

Le code d'une fonction récursive suit donc en général un schéma avec un if ... else :

🐍 Script Python

def fonction_rec(n):
    # n entier naturel pour simplifier
    if n in cas_de_base:  # cas de base
        return solution_directe
    else:
        return fonction_rec(reduction(n)) #avec reduction(n) < n

Arbre d'appels⚓︎

Méthode 1 : trace d'une fonction récursive

On peut représenter l'évaluation d'une fonction récursive par un arbre d'appels. Par exemple pour une fonction récursive de calcul du PGCD de deux entiers, on peut représenter ainsi les appels récursifs dans l'évaluation de PGCD(100, 45) lors de la phase de descente qui se termine par un cas de base :

arbre pgcd

La phase de remontée depuis un cas de base s'effectue en remplaçant à rebours chaque appel récursif par sa valeur :

Calculs à rebours	Arbre d'appels
PGCD(5,0)
PGCD(10,5)
PGCD(45, 10)
PGCD(100,45)

Maîtriser les compétences du programme⚓︎

Exercice 1

🎯 Analyser le fonctionnement d'un programme récursif

ÉnoncéSolution

On donne trois fonction récursives en Python qui s'appliquent à des entiers naturels.

🐍 Script Python

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

def g(n):
    return n * g(n - 1)  

def h(n):
    if n == 0:
        return 1
    else:
        n * h(n - 1)

Sans utiliser l'ordinateur, calculer les valeurs de f(0), f(1), f(2), f(10). On complètera progressivement un arbre d'appels qu'on remontera à rebours depuis le cas de base pour calculer la valeur de l'appel initial.
Sans utiliser l'ordinateur, prévoir ce qui se passe si on évalue f(-1), g(0), h(0), h(1) et enfin h(2).

Sans utiliser l'ordinateur, calculer les valeurs de f(0), f(1), f(2), f(10).
- 0 est le cas de base de la fonction récursive f donc par calcul direct f(0) vaut 1
- 1 n'est pas un cas de base, le calcul de f(1) se ramène par réduction à celui de f(1) = 1 * f(0). L'appel récursif se renvoie directement 1 car 0 est le cas de base donc f(1) = 1 * 1 = 1. Toujours par réductions successives, les appels récursifs s'imbriquent pour le calcul de f(2) :
  📋 Texte
```
f(2) = 2 * f(1) = 2 * (1 * f(0))  = 2 * (1 * 1) = 2 
```
Lors de l'évaluation de f(2), il faut bien comprendre que la séquence d'égalités est parcourue d'abord de gauche à droite (phase de descente) jusqu'à un cas de base, puis de droite à gauche (phase de remontée). * Pour f(10), les phases de descenter et remontée sont plus longues. On peut remarquer que le résultat est le produit des entiers successifs de 1 à 10, la factorielle de 10, notée 10!
📋 Texte
```
f(10) = 10 * f(9) = 10 * (9 * f(8)) = .... = 10 * (9 * (8 * (  ... * 1)))
```
Sans utiliser l'ordinateur, prévoir ce qui se passe si on évalue f(-1), g(0), h(0), h(1) et enfin h(2).
- -1 n'est pas un cas de base donc par réduction le calcul de f(-1) se ramène au calcul de f(-2) qui lui-même se ramène au calcul de f(-3) puis de f(-4) etc ... Comme le cas de base est 0 et que chaque réduction décrémente le paramètre de 1, on n'atteindra jamais le cas de base, c'est une descente infinie. Comme avec une boucle, une fonction récursive peut donc ne pas se terminer ! Ici cela se produit car le domaine de définition de la fonction Python est plus grand que celui de la fonction qu'on souhaite implémenter, il faudrait vérifier que le paramètre n passé à la fonction est un entier naturel, par exemple avec une assertion. On parle de programmation défensive.
🐍 Script Python
```
def f(n):
    assert isinstance(n, int) and n >= 0 # précondition
    if n == 0:
        return 1
    else:
        return n * f(n - 1)
```
- 0 n'est pas un cas de base pour la fonction récursive g donc par réduction le calcul de g(0) se ramène au calcul de g(-1) qui lui-même se ramène au calcul de g(-2) puis de f(-3) etc ... Nouvelle descente infinie. Ici, on n'atteindra jamais le cas de base, parce qu'il n'existe pas ! La fonction récursive ne se termine pas quel que soit son paramètre car le cas de base a été oublié !
- 0 est un cas de base pour la fonction récursive h et la valeur de h(0) est obtenue directement, c'est 1.
- 1 n'est pas un cas de base pour la fonction récursive h donc par réduction le calcul de h(1) se ramène au calcul de 1 * h(0) c'est-à-dire 1 * 1 puisque 0 est un cas de base. Notons que le calcul est effectué mais que h(1) ne renvoie rien car il n'y a pas de return dans la branche de réduction.
- 2 n'est pas un cas de base pour la fonction récursive h donc par réduction le calcul de h(2) se ramène au calcul de 2 * h(1). Mais la valeur renvoyée par h(1) est None puisqu'il n'y a pas de return dans la branche de réduction. Le calcul 2 * None n'a pas de sens car 2 et None ne sont pas de même type donc l'évaluation de h(2) provoque une erreur de type

Exercice 2

🎯 Écrire un programme récursif

On veut écrire une fonction récursive somme_carre qui prend en paramètre un entier naturel et qui renvoie la somme \(s(n)=0^{2}+1^2+2^2+3^2+...+n^2=\sum_{k=0}^{n}k^2\).

ÉnoncéSolution

Donner un ou plusieurs cas de base(s) dont la valeur peut être calculée directement.
Soit \(n\) un entier naturel strictement positif, exprimer \(s(n)\) en fonction de \(s(n-1)\). Cette réduction s'appelle en mathématiques une relation de récurrence.
Implémenter en Python la fonction récursive somme_carre dans l'IDE ci-dessous. Quelques tests unitaires sont fournis.
Calculer à la main somme_carre(5) à l'aide d'un arbre d'appels.
Si ce n'est déjà fait, insérer une assertion au début de la fonction pour vérifier que le paramètre est un entier naturel et que le domaine de définition de la fonction Python correspond à celui qu'on souhaite.
Donner une version itérative (avec une boucle) de cette fonction.

Évaluations restantes : ∞/∞

\(s(0)=0\) est le cas de base, plus généralement \(s(n)=n\) pour \(0 \leqslant n \leqslant 1\).
Pour tout entier \(n \geqslant 1\), on a réduit le problème de taille \(n\) au problème de taille \(n-1\) avec la relation de récurrence \(s(n)=s(n-1)+n^2\).

Implémentation en Python de la fonction récursive somme_carre:

🐍 Script Python

def somme_carre(n):
    if n <= 1:
        return n
    return n ** 2 + somme_carre(n - 1)

Calcul de somme_carre(5) à la main avec un arbre d'appels :

Avec programmation défensive :

🐍 Script Python

def somme_carre(n):
    assert isinstance(n, int) and n >= 0
    if n <= 1:
        return n
    return n ** 2 + somme_carre(n - 1)

Version itérative :

🐍 Script Python

def somme_carre_iter(n):
    assert isinstance(n, int) and n <= 1
    s = 0
    for k in range(1, n + 1):
        s = s + k ** 2
    return s

la fonction trace est cachée, elle prend en paramètre une fonction récursive et la transforme en une autre fonction de même nom pour qu'elle affiche la trace de l'exécution lorsqu'on appelle la fonction sur des paramètres. ↩