Newer
Older
---
jupytext:
text_representation:
extension: .md
format_name: myst
format_version: 0.13
jupytext_version: 1.11.5
kernelspec:
display_name: Python 3
language: python
name: python3
---
# Récursivité
* - Notion
- Savoir faire
- Observations
* - Récursivité
Analyser le fonctionnement d'un programme récursif.
- Des exemples relevant de domaines variés sont à privilégier.
```
## Définition
### Première approche
```{prf:definition} Fonction récursive
Une fonction récursive est une fonction qui s'appelle elle-même
```
```{code-cell} ipython3
def f():
print("Je suis une fonction récursive")
return f()
```
```{code-cell} ipython3
:tags: [remove-cell, remove-stderr]
import sys
l = sys.getrecursionlimit()
sys.setrecursionlimit(45)
:tags: [remove-stderr, copious-output]
f()
```
```{code-cell} ipython3
:tags: [remove-cell]
sys.setrecursionlimit(l)
```
Dans l'exemple ci-dessus, l'appel récursif ne termine pas et c'est un souci.
```{warning}
Pour éviter le cas précédent qui donne mauvaise réputation à la récursivité, on fera attention à **toujours** mettre une condition d'arrêt.
Ce problème est similaire au problème de la boucle `while` où la condition n'est jamais remplie.
```
+++
````{margin}
```{note} Acronymes récursifs
On peut signaler la présence d'acronymes récursifs en informatique, comme GNU is Not Unix ou PHP Hypertext Processor, ou encore VISA.
````{margin}
Attention à la récursivité non terminale, par exemple dans un interpréteur type bash.
```shell
:(){ :|:& };:
```
Le code suivant définit une fonction nommée `:`. Cette fonction s'appelle elle-même sans condition d'arrêt, mais de plus, elle envoie sa sortie standard sur l'entrée standard d'une nouvelle instance d'elle même. Cette dernière instance est mis en _background_ avec le `&`.
```{margin}
En bash, la définition d'une fonction se fait avec `f(var) { echo $var }` et s'appelle avec `f var`.
```
+++
## Récursivite avec cas de base
On peut consulter l'exemple suivant sur la somme des entiers naturels.