Newer
Older
---
jupytext:
formats: ipynb,md:myst
text_representation:
extension: .md
format_name: myst
format_version: 0.13
jupytext_version: 1.11.5
kernelspec:
display_name: Python 3 (ipykernel)
language: python
name: python3
---
# Récursivité
+++
## Parcours récursif d'une liste
+++
On va voir dans ce chapitre une nouvelle façon d'écrire des fonctions qui s'appellent elle même. On parle pour ça de __récursivité__ et de fonctions __récursives__. Il existe un lien assez fort entre ces fonctions récursives et la notion de récurrence vue en mathématiques, que nous ne développerons pas dans un premier temps.
+++
On importe la structure de liste telle que définie préalablement.
from cours.structures import Liste
```
On définit une première fonction qui s'appelle elle même.
def Dernier(liste, cdr):
if liste.estVide():
return cdr
else:
cdr = liste.queue()[0]
return Dernier(liste.queue()[1], cdr)
```
Cette fonction renvoie l'élément qui a été sortie en dernier tant que la liste n'est pas vide et sinon, elle renvoie le dernier élément retiré de la liste et la liste des éléments restants. On initialise cet élément à renvoyé (ici `cdr` par `None` de façon à ne rien renvoyer lorsque la liste est vide.
+++
Voyons sur quelques exemples.
liste = Liste(1,2,3,4)
Dernier(liste,None)
```
liste = Liste(1)
Dernier(liste,None)
```
liste = Liste()
Dernier(liste,None)
```
On peut visualiser l'appel de fonctions :
:tags: [remove-output]
##!pip3 install pycallgraph2
```
:tags: [remove-input]
from pycallgraph2 import PyCallGraph
from pycallgraph2 import Config
from pycallgraph2 import GlobbingFilter
from pycallgraph2.output import GraphvizOutput
with PyCallGraph(config=Config(max_depth=99, trace_filter=GlobbingFilter(exclude=['pycallgraph2.*','cours.*'],include=['*'])),output=GraphvizOutput(output_file='Dernier.png')):
liste = Liste(1,2,3,4)
Dernier(liste,None)
```
L'appel est bien récursif, comme peut le voir ici 
+++
## Exercices
+++
Écrire une fonction __itérative__ (non récursive) qui renvoie le dernier élément.
---
nbgrader:
grade: false
grade_id: cell-dfa6619c43c09f79
locked: false
schema_version: 3
solution: true
task: false
tags: [hide-input]
---
def Dernier(Liste):
### BEGIN SOLUTION
dernier = None
while not Liste.estVide():
dernier , Liste = Liste.queue()
return dernier
### END SOLUTION
```
Tester cette fonction sur quelques exemples.
---
nbgrader:
grade: true
grade_id: cell-7f4d473ae960c7b0
locked: true
points: 3
schema_version: 3
solution: false
task: false
---
liste = Liste(1,2,3,4)
assert Dernier(liste) == 4
liste = Liste(1)
assert Dernier(liste) == 1
liste = Liste()
assert Dernier(liste) == None
```
Écrire une fonction _itérative_ qui donne la longueur de la liste.
---
nbgrader:
grade: false
grade_id: cell-0f597f4d78475f08
locked: false
schema_version: 3
solution: true
task: false
tags: [hide-input]
---
def longueur(liste):
### BEGIN SOLUTION
l = 0
while not liste.estVide():
l = l + 1
liste = liste.queue()[1]
return l
### END SOLUTION
```
Tester cette fonction sur quelques exemples.
---
nbgrader:
grade: true
grade_id: cell-0ed22e89405a8268
locked: true
points: 3
schema_version: 3
solution: false
task: false
---
liste = Liste(1,2,3,4)
assert longueur(liste) == 4
liste = Liste(1)
assert longueur(liste) == 1
liste = Liste()
assert longueur(liste) == 0
```
Écrire une fonction _récursive_ qui donne la longueur de la liste.
---
nbgrader:
grade: false
grade_id: cell-b8220935e761d8c4
locked: false
schema_version: 3
solution: true
task: false
tags: [hide-input]
---
def longueur(liste):
### BEGIN SOLUTION
if liste.estVide():
return 0
else:
return longueur(liste.queue()[1]) + 1
### END SOLUTION
```
Tester cette fonction sur quelques exemples.
---
nbgrader:
grade: true
grade_id: cell-747993ea201bc286
locked: true
points: 3
schema_version: 3
solution: false
task: false
---
liste = Liste(1,2,3,4)
assert longueur(liste) == 4
liste = Liste(1)
assert longueur(liste) == 1
liste = Liste()
assert longueur(liste) == 0
```