La récursivité
==============
... une autre manière de penser un algorithme
<br><br>
*Ce document a été créé en collaboration avec ChatGPT (version 4o du 05 nov. 2024) pour transposer le cours correspondant (accessible [ici](recursivite)) en un diaporama.*
*Pour voir la conversation avec ChatGPT : [cliquer ici](https://chatgpt.com/share/67338c36-cc2c-8008-8dc3-1f8f951ad611)*
---
# Introduction
----
## Une image
<img class="r-stretch centre image-responsive" src="data/album_pink_floyd.jpg" alt="pochette album">
Pochette de l'album _Ummagumma_ de Pink Floyd
----
## Quelques définitions
- **Récursivité** : Démarche qui fait référence à l'objet même de la démarche.
- **Récursivité en programmation** : Fait pour un objet de s'appeler lui-même.
- Un objet est **récursif** s'il se définit par lui-même.
- Une construction est **récursive** si elle se définit par elle-même.
----
## Exemples
- Décrire un processus dépendant de données en utilisant le même processus sur des données *plus simples* (c'est ce que nous allons faire !).
- Montrer une image contenant des images similaires (ex. _Ummagumma_).
- Faire pointer un article vers lui-même ou un article qui pointe vers lui, ou vers un article qui, par une succession de pointeurs, pointe vers l'article dont on est parti.
---
# Retour sur les listes
----
## Constructions récursives dans les listes
- Le constructeur `construit(e, L)` crée une liste avec `e` comme tête et `L` comme queue.
- Ex. pour créer la liste de nombres `5, 3, 8, 1` :
```python
construit(5, construit(3, construit(8, construit(1, listevide()))))
```
- Représentation en `tuple` :
```python
(5, (3, (8, (1, None))))
```
----
## Fonction `dernier(L)`
- Opération `dernier(L)` renvoie le dernier élément d'une liste `L`.
- Version itérative (déjà écrite) :
```python
def dernier(L):
while reste(L) != listevide():
L = reste(L)
return premier(L)
```
----
### Version récursive de `dernier`
- Commençons par réfléchir ...
- Comment obtenir le dernier élément d'une liste `L` ?
- <span class="fragment">Si le reste de `L` est vide :</span> <span class="fragment">`dernier(L)` = </span> <span class="fragment">`premier(L)`</span>
- <span class="fragment">Sinon,</span> <span class="r-stack"><span class="fragment">`dernier(L) = dernier(...)`</span><span class="fragment">`dernier(L) = dernier(reste(L))`</span></span>
----
### Version récursive de `dernier`
- Exemple : trouver `dernier(5, 3, 8, 1)`
```plaintext
dernier(5, 3, 8, 1) = dernier(3, 8, 1)
= dernier(8, 1)
= dernier(1) # le reste est vide
= 1
```
----
### Analyse
```python {.line-numbers} []
def dernier(L):
if reste(L) == listevide():
return premier(L)
else:
return dernier(reste(L))
```
- Cette fonction est bien **récursive** puisqu'elle s'appelle elle-même (ligne 5)
- On trouve ici le schéma classique d'un algorithme récursif :
- On définit le **cas de base** (ici lorsque le reste est vide) qui est un cas pour lequel on peut donner le résultat facilement et qui fournit donc une **condition d'arrêt** des appels récursifs (indispensable !) ;
- Sinon, on fait un **appel récursif** à la fonction mais sur une donnée plus petite (ici une liste plus petite).
----
### Analyse
```python {.line-numbers} []
def dernier(L):
if reste(L) == listevide():
return premier(L)
else:
return dernier(reste(L))
```
- Les appels récursifs se font sur des données dont la **taille diminue** : on est sûr d'aboutir au *cas de base* qui stoppe les appels récursifs et assure la **terminaison** de l'algorithme
---
# Déroulement d'une fonction récursive
----
## Déroulement d'une fonction récursive
- Chaque appel récursif **met en pause** l'exécution en attente du résultat de l'appel suivant.
- Concrètement, il y a **2 phases** :
- **Dépliage** (ou **descente**) : Les appels sont tour à tour mis en pause jusqu'au dernier appel qui fourni un resultat.
- **Évaluation** : Le dernier résultat est renvoyé en remontant à l'appel précédent, qui l'utilise pour calculer son propre résultat et le renvoyer à l'appel précédent, etc.
----
### Exemple de `dernier`
```python
def dernier(L):
if reste(L) == listevide():
return premier(L)
else:
return dernier(reste(L))
```
- Calcul de `dernier((5, (3, (8, None)))` :
<img class="centre image-responsive" src="data/deroulement_dernier.png">
----
### Exemple de `dernier`
```python {.line-numbers} []
def dernier(L):
if reste(L) == listevide():
return premier(L)
else:
return dernier(reste(L))
```
- Autre représentation :
<img class="centre image-responsive r-stretch" src="data/deroulement_execution.png">
----
### ✍️ À faire
Exercice 1
---
# Autre exemple : calcul de puissances
----
## Fonction récursive pour `2^n`
- Calcul de $2^n$ en récursif :
- Cas de base ($n=0$) : $2^0 = 1$
- Sinon : $2^n = 2 \times 2^{n-1}$ (on se ramène à une puissance plus petite)
- Résumé :
<img src="data/definition_deux_puissance.png">
----
## Fonction récursive pour `2^n`
<img src="data/definition_deux_puissance.png">
- Implémentation en Python :
```python
def deux_puissance(n):
if n == 0: # cas de base
return 1
else: # sinon appel récursif avec un argument plus petit
return 2 * deux_puissance(n-1)
```
```python
>>> deux_puissance(3)
8
```
----
## Déroulement de `deux_puissance`
**Arbre d'appel**
<img src="data/deroulement_deux_puissance.png">
----
**Autre représentation**
```
deux_puissance(3)
-> 2 * deux_puissance(2) -> DEPLIAGE
-> -> 2 * 2 * deux_puissance(1)
-> -> -> 2 * 2 * 2 * deux_puissance(0)
.......................................................
<- <- <- 2 * 2 * 2 * 1
<- <- 2 * 2 * 2 <- EVALUATION
<- 2 * 4
8
```
----
**Autre représentation (bis)**
```
deux_puissance(3)
2 * deux_puissance(2) = ?
appel à deux_puissance(2)
2 * deux_puissance(1) = ? DEPLIAGE
appel à deux_puissance(1)
2 * deux_puissance(0) = ?
appel à deux_puissance(0)
......................................................
renvoie 1
2 * 1
renvoie 2
2 * 2 EVALUATION
renvoie 4
2 * 4
renvoie 8
```
----
**Empilement des appels**
<img class="centre image-responsive r-stretch" src="data/pile_execution.png" alt="pile d'exécution">
----
**Utilisation d'outils**
- Python Tutor : [lien vers pythontutor](https://www.pythontutor.com/visualize.html#code=def%20deux_puissance%28n%29%3A%0A%20%20%20%20if%20n%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20return%201%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20return%202%20*%20deux_puissance%28n-1%29%0A%0Adeux_puissance%283%29&cumulative=true&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false).
- Encore mieux : le logiciel **Thonny**
----
### ✍️ À faire
Exercices 2, 3, 4, 5
---
# Récursif vs Itératif
----
## Récursif vs Itératif
- Tout programme récursif peut être transformé en un programme itératif.
- Réciproquement, tout programme itératif peut être transformé en récursif.
- **Question** : Quelle méthode privilégier pour écrire un programme ?
----
## Exemple : Puissances de deux
**Version itérative**
```python
def deux_puissance_iter(n):
reponse = 1
for i in range(n):
reponse = reponse * 2
return reponse
```
**Version récursive**
```python
def deux_puissance_rec(n):
if n == 0:
return 1
else:
return 2 * deux_puissance_rec(n-1)
```
----
# Méthodes de Raisonnement
- En itératif :
- On pense à **la suite des instructions pour progresser des données vers le résultat**.
- En récursif :
- On **commence par exprimer le résultat à obtenir**.
- On définit les **cas de base** et le (ou les) **cas récursif**.
- Les deux approches sont à la base de :
- *Programmation impérative* (itératif)
- *Programmation fonctionnelle* (récursif)
----
## Avantages de la Récursivité
- **Lisibilité** : souvent plus élégante (question de goût) et concise.
- **Efficace pour** :
- Algorithmes sur des structures de données (listes, arbres, graphes).
- Algorithmes « diviser pour régner ».
----
## Inconvénients de la Récursivité : Efficacité
- **En temps** :
- Un programme récursif doit être traduit en itératif par le compilateur (un processeur est fondamentalement itératif)
- L'exécution est souvent un peu plus lente, mais d'ordre de grandeur similaire.
----
## Inconvénients de la Récursivité : Efficacité (suite)
- **En espace** :
- Les appels récursifs doivent stocker le contexte (paramètres, adresse de retour).
- Ces contextes sont empilés (*pile* d'exécution, on le voit bien avec Thonny)
- La mémoire requise pour la pile peut causer des erreurs de débordement.
----
## Limites en Python
- Python permet d'écrire des fonctions récursives mais n'est pas optimisé pour faire du récursif comparé à d'autres langages spécialisés dans le récursif
- Le nombre d'appels récursifs est limité (on peut augmenter la valeur néanmoins)
- Dépassement : une erreur `RecursionError` est levée.
- Exemple :
```python
>>> deux_puissance_rec(1000)
RecursionError: maximum recursion depth exceeded in comparison
```
- Version itérative réussit :
```python
>>> deux_puissance_iter(1000) # Donne le résultat sans erreur
... # un très grand nombre
```
---
# Bilan
- Un programme est dit **récursif** lorsqu'il s'appelle lui-même.
- La récursivité est un **principe algorithmique** :
- La solution d’un problème est exprimée par un problème similaire mais sur un objet plus petit.
- Pour une fonction récursive, il faut :
- **Définir le(s) cas de base**.
- **Déterminer les cas récursifs**.
----
# Bilan (suite)
- Avantages de la récursivité (vs. itératif):
- peut être vue comme plus élégante, concise et compréhensible que l'itératif.
- Inconvénients de la récursivité (vs. itératif) :
- efficacité en temps : un peu plus lent mais même ordre de grandeur
- efficacité en espace (mémoire) :
- le contexte des appels récursifs en pause doit être gardé en mémoire (dans une *pile*)
- peut occasionner des débordements de la pile (*stack overflow*)
---
**Références :**
- Documents ressources de l'équipe éducative du DIU EIL, Université de Nantes, Christophe JERMANN et Christophe DECLERCQ, licence CC BY-NC-SA.
---
Germain BECKER, Lycée Mounier, ANGERS
Ressource éducative libre distribuée sous [Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International](http://creativecommons.org/licenses/by-nc-sa/4.0/)
