01seq03_structures_recursivite.md

---
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.

```{code-cell} ipython
from cours.structures import Liste
```

On définit une première fonction qui s'appelle elle même.

```{code-cell} ipython
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.

```{code-cell} ipython
liste = Liste(1,2,3,4)
Dernier(liste,None)
```

```{code-cell} ipython
liste = Liste(1)
Dernier(liste,None)
```

```{code-cell} ipython
liste = Liste()
Dernier(liste,None)
```

On peut visualiser l'appel de fonctions :

```{code-cell} ipython
:tags: [remove-output]

##!pip3 install pycallgraph2
```

```{code-cell} ipython
: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 ![](Dernier.png)

+++

## Exercices

+++

Écrire une fonction __itérative__ (non récursive) qui renvoie le dernier élément.

```{code-cell} ipython
def Dernier(Liste):
    pass
```

```{code-cell} ipython
---
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.

```{code-cell} ipython
---
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.

```{code-cell} ipython
def longueur(liste):
    pass
```

```{code-cell} ipython
---
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.

```{code-cell} ipython
---
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.

```{code-cell} ipython
def longueur(liste):
    pass
```

```{code-cell} ipython
---
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.

```{code-cell} ipython
---
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
```