03-recursivite-listes.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# dé-commenter cette ligne si nbtutor est installé\n",
    "# %load_ext nbtutor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from callstats import CallRecorder\n",
    "from sys import setrecursionlimit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from IPython.core.display import HTML\n",
    "\n",
    "def _set_css_style(css_file_path):\n",
    "   \"\"\"\n",
    "   Read the custom CSS file and load it into Jupyter.\n",
    "   Pass the file path to the CSS file.\n",
    "   \"\"\"\n",
    "\n",
    "   styles = open(css_file_path, \"r\").read()\n",
    "   s = '<style>%s</style>' % styles     \n",
    "   return HTML(s)\n",
    "\n",
    "_set_css_style('custom/custom.css')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<div style='width:20em'><img src='img/logo-igm.png'></div>\n",
    "<div style='font-size:larger'><strong>Algorithmique et programmation 2</strong><br>\n",
    "L1 Mathématiques - L1 Informatique<br>\n",
    "Semestre 2\n",
    "</div>\n",
    "\n",
    "# Récursivité et listes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "1. Un type de données récursif : les listes chaînées\n",
    "2. Fonctions récursives sur les listes chaînées\n",
    "3. Récursivité et listes Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Un type de données récursif : les listes chaînées"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Rappel : définition récursive d'une fonction\n",
    "\n",
    "On distingue un ou plusieurs cas \"de base\" et un cas \"général\"\n",
    "\n",
    "Factorielle :\n",
    "\n",
    "$$\n",
    "n! = \\begin{cases}\n",
    "      1 \\text{ si $n = 0$}\\\\\n",
    "      n \\times (n-1)! \\text{ sinon}\n",
    "    \\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Nouveauté : définir un type récursivement\n",
    "\n",
    "**Idée :** une **liste** est\n",
    "- Soit vide (elle ne contient aucun élément)\n",
    "- Soit constituée d'un premier élément et de la **liste** des éléments suivants\n",
    "\n",
    "On définit l'ensemble des listes en faisant référence... à l'ensemble des listes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "On appelle ces listes des **listes (simplement) chaînées** :\n",
    "\n",
    "![liste chaînée](img/Singly-linked-list.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### En Python\n",
    "\n",
    "On peut choisir de représenter :\n",
    "\n",
    "- La liste vide par `None`\n",
    "- La liste constituée du premier élément `tete` suivi de la liste d'éléments `suite` par le tuple `(tete, suite)`\n",
    "\n",
    "**Remarque importante :** on représente ici des listes **immutables** !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Exemples :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "vide = None  # liste à 0 éléments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "# %%nbtutor -r -f\n",
    "\n",
    "nombres = (12, (99, (37, None)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "# %%nbtutor -r -f\n",
    "\n",
    "saisons = ('printemps', \n",
    "              ('été', \n",
    "                  ('automne', \n",
    "                      ('hiver', None))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Attention :** ce ne sont pas du tout les listes habituelles de Python ! \n",
    "\n",
    "Pour éviter la confusion on distinguera\n",
    "- **\"listes chaînées\"** ou **\"listes récursives\"**\n",
    "- **\"listes Python\"** ou **\"listes classiques\"** ou **\"listes natives\"**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Fonctions utilitaires"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def liste_vide():\n",
    "    \"\"\"\n",
    "    Renvoie une liste récursive vide.\n",
    "    \"\"\"\n",
    "    return None\n",
    "\n",
    "def est_vide(r_liste):\n",
    "    \"\"\"\n",
    "    Renvoie True si r_liste est vide, False sinon.\n",
    "    \"\"\"\n",
    "    return r_liste == None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "r_liste = liste_vide()\n",
    "est_vide(r_liste)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def ajout_debut(v, r_liste):\n",
    "    \"\"\"\n",
    "    Renvoie une nouvelle liste récursive en ajoutant v au début de r_liste.\n",
    "\n",
    "    >>> ajout_debut('a', liste_vide())\n",
    "    ('a', None)\n",
    "\n",
    "    >>> ajout_debut('a', ajout_debut('b', liste_vide()))\n",
    "    ('a', ('b', None))\n",
    "    \"\"\"\n",
    "    return (v, r_liste)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ajout_debut('a', \n",
    "    ajout_debut('b', \n",
    "        ajout_debut('c', \n",
    "            liste_vide())))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from doctest import testmod\n",
    "testmod()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def tete(r_liste):\n",
    "    \"\"\"\n",
    "    Renvoie l'élément de tête de r_liste.\n",
    "\n",
    "    ATTENTION : plante si r_liste est vide !\n",
    "\n",
    "    >>> tete(('a', ('b', None)))\n",
    "    'a'\n",
    "\n",
    "    >>> tete(None)\n",
    "    Traceback (most recent call last):\n",
    "    ...\n",
    "    TypeError: 'NoneType' object is not subscriptable\n",
    "    \"\"\"\n",
    "    return r_liste[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def suite(r_liste):\n",
    "    \"\"\"\n",
    "    Renvoie r_liste privée de son élément de tête.\n",
    "\n",
    "    ATTENTION : plante si r_liste est vide !\n",
    "\n",
    "    >>> suite(('a', ('b', None)))\n",
    "    ('b', None)\n",
    "\n",
    "    >>> suite(None)\n",
    "    Traceback (most recent call last):\n",
    "    ...\n",
    "    TypeError: 'NoneType' object is not subscriptable\n",
    "    \"\"\"\n",
    "    return r_liste[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nombres = (12, (99, (37, None)))\n",
    "tete(nombres)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "suite(nombres)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Parcours (récursif) de listes (récursives)\n",
    "\n",
    "-   **Idée :** traiter un élément, puis appel récursif sur le reste, en déduire un résultat\n",
    "-   **Cas d'arrêt :** liste vide, ou liste réduite à un élément"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<img src=\"img/reclistes.png\" width=70%></img>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "Nombreuses variantes possibles *(dans l'autre sens, deux éléments à la fois...)*  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Calculer la longueur d'une liste récursive\n",
    "\n",
    "#### Algorithme\n",
    "\n",
    "La longueur d'une liste `r_liste` est :\n",
    "- 0 si `r_liste` est vide\n",
    "- la longueur de la liste `suite` plus 1 si `r_liste` est de la forme `(tete, suite)`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Implémentation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def longueur(r_liste):\n",
    "    \"\"\"\n",
    "    Renvoie le nombre d'éléments de r_liste.\n",
    "\n",
    "    >>> longueur(liste_vide())\n",
    "    0\n",
    "\n",
    "    >>> longueur(('a', ('b', ('c', None))))\n",
    "    3\n",
    "    \"\"\"\n",
    "    if est_vide(r_liste):\n",
    "        return 0\n",
    "    else:\n",
    "        return 1 + longueur(suite(r_liste))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "vide = liste_vide()\n",
    "longueur(vide)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "nombres = (12, (99, (37, None)))\n",
    "longueur(nombres)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "saisons = ('printemps', ('été', ('automne', ('hiver', None))))\n",
    "longueur(saisons)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Rechercher un élément dans une liste récursive\n",
    "\n",
    "Soit `r_liste` une liste récursive et `v` une valeur quelconque, on veut savoir si `v` apparaît dans `r_liste`.\n",
    "\n",
    "#### Algorithme\n",
    "\n",
    "- si `r_liste` est vide : c'est **faux**\n",
    "- si `r_liste` est de la forme `(tete, suite)` avec `tete == v` : c'est **vrai**\n",
    "- si `r_liste` est de la forme `(tete, suite)` avec `tete != v` : on recherche `v` dans `suite`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Implémentation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def est_dans(v, r_liste):\n",
    "    \"\"\"\n",
    "    Renvoie True si v apparaît dans r_liste, False sinon.\n",
    "\n",
    "    >>> est_dans('b', None)\n",
    "    False\n",
    "\n",
    "    >>> est_dans('b', ('a', ('b', ('c', None))))\n",
    "    True\n",
    "\n",
    "    >>> est_dans('d', ('a', ('b', ('c', None))))\n",
    "    False\n",
    "    \"\"\"\n",
    "    if est_vide(r_liste):\n",
    "        return False\n",
    "    elif tete(r_liste) == v:\n",
    "        return True\n",
    "    else:\n",
    "        return est_dans(v, suite(r_liste))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "est_dans(\"automne\", saisons)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "est_dans(\"juillet\", saisons)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def est_dans(v, r_liste):\n",
    "    if r_liste is None:\n",
    "        return False\n",
    "    elif r_liste[0] == v:\n",
    "        return True\n",
    "    else:\n",
    "        return est_dans(v, r_liste[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Chercher la position d'un élément dans une liste récursive\n",
    "\n",
    "Soit `r_liste` une liste récursive et `v` une valeur quelconque, on veut savoir à quelle position `v` apparaît pour la première fois dans `r_liste` (en comptant à partir de 0). \n",
    "\n",
    "On fixera par convention le résultat à `None` si la liste ne contient pas `v`, en particulier si la liste est vide."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def premier_indice(v, r_liste):\n",
    "    if est_vide(r_liste):\n",
    "        return None\n",
    "    elif tete(r_liste) == v:\n",
    "        return 0\n",
    "    else:\n",
    "        tmp = premier_indice(v, suite(r_liste))\n",
    "        if tmp == None:\n",
    "            return None\n",
    "        else:\n",
    "            return tmp + 1\n",
    "\n",
    "premier_indice(\"automne\", saisons)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "saisons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Algorithme\n",
    "\n",
    "Si `r_liste` est vide, le résultat est `None`. Dans le cas contraire, on suppose que `r_liste` est de la forme `(tete, suite)`.\n",
    "- Si `tete == v` : le résultat est `0`\n",
    "- Si `tete != v` : le résultat est 1 + la poisition de `v` dans `suite`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Implémentation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def premier_indice(v, r_liste):\n",
    "    \"\"\"\n",
    "    Renvoie l'indice de première occurrence de c dans r_liste, ou None.\n",
    "    \n",
    "    >>> premier_indice('a', ('a', ('a', ('c', None))))\n",
    "    0\n",
    "\n",
    "    >>> premier_indice('c', ('a', ('a', ('c', None))))\n",
    "    2\n",
    "\n",
    "    >>> premier_indice('d', ('a', ('a', ('c', None)))) == None\n",
    "    True\n",
    "    \"\"\"\n",
    "    if est_vide(r_liste):\n",
    "        return None\n",
    "    elif tete(r_liste) == v:\n",
    "        return 0\n",
    "    else:\n",
    "        res = premier_indice(v, suite(r_liste))\n",
    "        if res is None: return None\n",
    "        return 1 + res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "r_liste = (0, (1, (0, (1, (0, None)))))\n",
    "premier_indice(1, r_liste)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "premier_indice(\"automne\", saisons)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "premier_indice(\"juillet\", saisons)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def premier_indice_v2(v, r_liste, decalage):\n",
    "    \"\"\"\n",
    "    Renvoie l'indice de première occurrence de c dans r_liste, ou None.\n",
    "    \n",
    "    >>> premier_indice_v2('a', ('a', ('a', ('c', None))), 0)\n",
    "    0\n",
    "\n",
    "    >>> premier_indice_v2('c', ('a', ('a', ('c', None))), 0)\n",
    "    2\n",
    "\n",
    "    >>> premier_indice_v2('d', ('a', ('a', ('c', None))), 0) == None\n",
    "    True\n",
    "    \"\"\"\n",
    "    if est_vide(r_liste):\n",
    "        return None\n",
    "    elif tete(r_liste) == v:\n",
    "        return decalage\n",
    "    else:\n",
    "        return premier_indice_v2(v, suite(r_liste), decalage+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "premier_indice_v2(1, r_liste, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "premier_indice_v2(\"automne\", saisons, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Variantes\n",
    "\n",
    "##### Recherche du dernier indice où apparaît un élément"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def dernier_indice(v, r_liste):\n",
    "    \"\"\"\n",
    "    Renvoie l'indice de dernière occurrence de c dans r_liste, ou None.\n",
    "    \n",
    "    >>> dernier_indice('a', ('a', ('a', ('c', None))))\n",
    "    1\n",
    "\n",
    "    >>> dernier_indice('c', ('a', ('a', ('c', None))))\n",
    "    2\n",
    "\n",
    "    >>> dernier_indice('d', ('a', ('a', ('c', None)))) == None\n",
    "    True\n",
    "    \"\"\"\n",
    "    if est_vide(r_liste):\n",
    "        return None\n",
    "    else:\n",
    "        res = dernier_indice(v, suite(r_liste))\n",
    "        if tete(r_liste) != v and res == None:\n",
    "            return None\n",
    "        elif res == None:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "r_liste = (0, (1, (0, (1, (0, None)))))\n",
    "dernier_indice(1, r_liste)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "dernier_indice(2, r_liste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "##### Liste des indices où apparaît un élément"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def liste_indices(v, r_liste):\n",
    "    if est_vide(r_liste):\n",
    "        return liste_vide()\n",
    "    else:\n",
    "        res = liste_indices(v, suite(r_liste))\n",
    "        if tete(r_liste) == v:\n",
    "            return ajout_debut(0, res)\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "r_liste = (0, (1, (0, (1, (0, None)))))\n",
    "liste_indices(0, r_liste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "##### Deuxième tentative"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def increment(r_liste):\n",
    "    if est_vide(r_liste):\n",
    "        return liste_vide()\n",
    "    else:\n",
    "        res = increment(suite(r_liste))\n",
    "        return ajout_debut(tete(r_liste) + 1, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "increment((3, (12, (4, None))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def liste_indices(v, r_liste):\n",
    "    if est_vide(r_liste):\n",
    "        return liste_vide()\n",
    "    else:\n",
    "        res = liste_indices(v, suite(r_liste))\n",
    "        res = increment(res)\n",
    "        if tete(r_liste) == v:\n",
    "            return ajout_debut(0, res)\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "r_liste = (0, (1, (0, (1, (0, None)))))\n",
    "liste_indices(0, r_liste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "##### Dernière tentative"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def liste_indices(v, r_liste, decalage):\n",
    "    if est_vide(r_liste):\n",
    "        return liste_vide()\n",
    "    else:\n",
    "        res = liste_indices(v, suite(r_liste), decalage+1)\n",
    "        if tete(r_liste) == v:\n",
    "            return ajout_debut(decalage, res)\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "r_liste = (0, (1, (0, (1, (0, None)))))\n",
    "liste_indices(0, r_liste, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Convertir une liste récursive en chaîne de caractères\n",
    "\n",
    "... par exemple pour pouvoir l'afficher joliment.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "\n",
    "#### Algorithme\n",
    "\n",
    "- si la liste est vide, on renvoie une chaîne par défaut `\"()\"`\n",
    "- sinon, on convertit la tête et (récursivement) la suite de la liste et on renvoie leur concaténation (en incluant un séparateur)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Implémentation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def liste_vers_chaine(r_liste):\n",
    "    if est_vide(r_liste):\n",
    "        return \"()\"\n",
    "    else:\n",
    "        return str(tete(r_liste)) + \" -> \" + liste_vers_chaine(suite(r_liste))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "liste_vers_chaine(nombres)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "***Remarque :** Cette implémentation n'est pas très efficace, on verra pourquoi prochainement.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Renverser une liste chaînée\n",
    "\n",
    "Il s'agit de construire une *nouvelle liste* contenant les mêmes éléments en ordre inverse. Cette opération est un peu plus difficile."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Algorithme\n",
    "- si la liste est vide, on renvoie une liste vide\n",
    "- sinon, on renverse la suite de la liste, et on y ajoute la tête comme dernier élément"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Implémentation\n",
    "\n",
    "*Problème :* on sait déjà ajouter un élément en début de liste avec `ajout_debut`, mais pas en fin — il faut une nouvelle fonction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def ajout_fin(v, r_liste):\n",
    "    if est_vide(r_liste):\n",
    "        return ajout_debut(v, r_liste)\n",
    "    else:\n",
    "        t, s = tete(r_liste), suite(r_liste)\n",
    "        return ajout_debut(t, ajout_fin(v, s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "nombres = (12, (99, (37, None)))\n",
    "ajout_fin(5, nombres)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def renverser(r_liste):\n",
    "    if est_vide(r_liste):\n",
    "        return r_liste\n",
    "    else:\n",
    "        acc = renverser(suite(r_liste))\n",
    "        return ajout_fin(tete(r_liste), acc)  # coûteux !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "renverser(nombres)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "*Défaut :* Cette implémentation parcourt la liste entièrement à chaque nouvel élément à ajouter à `res` ! Cela peut vite devenir trop coûteux"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Deuxième essai"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def renverser2(r_liste):\n",
    "    return renverser_aux(r_liste, liste_vide())\n",
    "\n",
    "def renverser_aux(r_liste, acc):\n",
    "    if est_vide(r_liste):\n",
    "        return acc\n",
    "    else:\n",
    "        acc = ajout_debut(tete(r_liste), acc)\n",
    "        return renverser_aux(suite(r_liste), acc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "renverser2(nombres)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Commentaire sur la performance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "Dans la seconde implémentation, on utilise seulement `ajout_debut`, qui ne parcourt pas la liste. Pour vérifier notre intuition sur la performance de ces deux variantes, on peut les chronométrer sur une liste suffisamment grande :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def premiers_entiers(n):\n",
    "    acc = liste_vide()\n",
    "    for i in range(n-1, -1, -1):\n",
    "        acc = ajout_debut(i, acc)\n",
    "    return acc\n",
    "\n",
    "grande_liste = premiers_entiers(2000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "%timeit renverser(grande_liste)\n",
    "%timeit renverser2(grande_liste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Pour aller plus loin\n",
    "\n",
    "- Toutes les fonctions montrées ci-dessus peuvent aussi être écrites facilement avec des boucles `while` (essayer !)\n",
    "- Il reste à analyser la complexité des opérations sur les listes récursives, et la comparer avec les listes Python *(à venir dans un prochain épisode !)*\n",
    "- On peut concevoir des structures de données récursives plus complexes (arbres, etc.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Récursivité sur les listes Python\n",
    "\n",
    "**Question :** peut-on aussi écrire des fonctions récursives pour parcourir des listes Python ?\n",
    "\n",
    "La réponse est bien sûr **oui**, mais avec quelques points de vigilance..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Rappel : structure des listes Python\n",
    "\n",
    "Les listes Python sont très différents des listes chaînées. Ce sont\n",
    "- des **tableaux contigus** (rangées de « cases » les unes à côté des autres en mémoire)\n",
    "- redimensionnés automatiquement selon le besoin\n",
    "- programmés dans un langage de bas niveau, et très rapide\n",
    "\n",
    "Il faut donc être très prudent quand on compare ces structures de données."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Quelques exemples de fonctions récursives"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "Reprenons un exemple traité plus haut :\n",
    "\n",
    "**Recherche** : Écrivez une fonction Python prenant en argument une liste et un objet quelconque, et renvoyant `True` si l'objet est dans la liste, `False` sinon... *sans utiliser de boucle ni le mot-clé `in`*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Premier essai : avec une *slice*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def est_dans_v1(elem, lst):\n",
    "    if lst[0] == elem:\n",
    "        return True\n",
    "    else:\n",
    "        return est_dans_v1(elem, lst[1:len(lst)])\n",
    "    \n",
    "est_dans_v1(0, [1, 2, 3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "*Problème :* oubli d'un cas d'arrêt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Second essai : *slice* et arrêt sur liste vide"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def est_dans_v2(elem, lst):\n",
    "    if len(lst) == 0:\n",
    "        return False\n",
    "    elif lst[0] == elem:\n",
    "        return True\n",
    "    else:\n",
    "        return est_dans_v2(elem, lst[1:])\n",
    "        \n",
    "est_dans_v2(0, [1, 2, 3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "*Problème :* calculer `lst[1:]` à chaque appel est **trop coûteux**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "setrecursionlimit(20000)\n",
    "lst = [0] * 10**4\n",
    "%timeit est_dans_v2(1, lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Troisième essai : paramètre supplémentaire"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def est_dans_v3(elem, lst, debut):\n",
    "    if debut >= len(lst):\n",
    "        return False\n",
    "    elif lst[debut] == elem:\n",
    "        return True\n",
    "    else:\n",
    "        return est_dans_v3(elem, lst, debut+1)  \n",
    "    \n",
    "lst = ['a', 'b', 'c']\n",
    "est_dans_v3('d', lst, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<img src=\"img/reclistes2.png\" width=70%></img>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- Avantage : travaille toujours sur la même liste\n",
    "- **Beaucoup** plus rapide"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lst = [0] * 10**4\n",
    "%timeit est_dans_v3(1, lst, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "- Défaut : change la signature de la fonction (3 paramètres)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Variante : paramètre par défaut"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def est_dans_v4(elem, lst, debut=0):\n",
    "    if debut >= len(lst):\n",
    "        return False\n",
    "    elif lst[debut] == elem:\n",
    "        return True\n",
    "    else:\n",
    "        return est_dans_v4(elem, lst, debut+1)  \n",
    "    \n",
    "lst = ['a', 'b', 'c']\n",
    "est_dans_v4('b', lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "-   Avantage : travaille toujours sur la même liste\n",
    "-   Valeur par défaut de `debut` si absent (`debut=0`)\n",
    "-   Appel sans le troisième argument : cherche sur toute la liste"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Conclusion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Pourquoi programmer des fonctions récursives ?\n",
    "\n",
    "-   On peut tout calculer de cette façon (sans boucles !)\n",
    "-   Certains problèmes plus simples à résoudre\n",
    "    \n",
    "    -   Bien adapté à des structures de données récursives\n",
    "    -   Solutions souvent plus concises et compréhensibles\n",
    "    -   Algorithmes parfois plus faciles à analyser\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "-   Certains le sont beaucoup moins...\n",
    "    \n",
    "    -   Complexité parfois plus difficile à évaluer\n",
    "    -   Opérations parfois inadaptées (ex : listes Python)\n",
    "    \n",
    "-   Peut entraîner un surcoût\n",
    "    \n",
    "    -   Temps de gestion de la pile\n",
    "    -   Espace mémoire pour chaque appel imbriqué\n",
    "    -   Recopies si on n'est pas prudent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Bilan de la récursivité\n",
    "\n",
    "-   Avantages:\n",
    "    \n",
    "    - $\\checkmark$ simplifie la vie quand on a compris le ``truc''\n",
    "    - $\\checkmark$ code souvent plus court et donc plus lisible\n",
    "    \n",
    "-   Inconvénients:\n",
    "\n",
    "    - $\\times$ il faut comprendre le truc...\n",
    "    - $\\times$ tous les langages ne s'y prêtent pas aussi bien\n",
    "    - $\\times$ souvent moins performant *($\\rightarrow$ dérécursification, récursion terminale...)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## <img src='img/non-exigible.png' style='display:inline; width:1.5em'> Raffinement du parcours de listes *(non exigible)*\n",
    "\n",
    "**Problème :** \n",
    "- Le parcours récursif de listes Python vu précédemment recopie une portion de la liste à chaque appel (tous les éléments sauf 1) !\n",
    "- C'est très coûteux en temps d'exécution et en mémoire."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "#%%nbtutor -r -f -d 11 -i\n",
    "\n",
    "def est_dans_v2(lst, elem):\n",
    "    if len(lst) == 0:\n",
    "        return False\n",
    "    elif lst[0] == elem:\n",
    "        return True\n",
    "    else:\n",
    "        return est_dans_v2(lst[1:], elem)\n",
    "\n",
    "est_dans_v2(list(range(10)), 14)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Cela revient (en plus rapide) à écrire une fonction `queue(lst)` qui renvoie une copie de `lst` privée de son premier élément :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def queue(lst):\n",
    "    res = []\n",
    "    for i in range(1, len(lst)):\n",
    "        res.append(lst[i])\n",
    "    return res\n",
    "\n",
    "def est_dans_2_bis(lst, elem):\n",
    "    if len(lst) == 0:\n",
    "        return False\n",
    "    elif lst[0] == elem:\n",
    "        return True\n",
    "    else:\n",
    "        return est_dans_2_bis(queue(lst), elem)\n",
    "    \n",
    "est_dans_2_bis(list(range(10)), 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "est_dans_2_bis([0, 0, 0, 0, 0], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "est_dans_2_bis([0, 0, 0, 0, 1], 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Exercice :** compter le nombre d'appels à la fonction `append`\n",
    "-   au cours de l'appel `est_dans_2_bis([0, 0, 0, 0, 0], 1)`\n",
    "-   au cours de l'appel `est_dans_2_bis([0] * n, 1)` pour `n` un naturel quelconque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def queue(lst):\n",
    "    res = []\n",
    "    cpt = 0\n",
    "    for i in range(1, len(lst)):\n",
    "        res.append(lst[i])\n",
    "        cpt += 1\n",
    "    return res, cpt\n",
    "\n",
    "def est_dans_2_ter(lst, elem):\n",
    "    if len(lst) == 0:\n",
    "        return False, 0\n",
    "    elif lst[0] == elem:\n",
    "        return True, 0\n",
    "    else:\n",
    "        tmp, cpt = queue(lst)\n",
    "        res, cpt2 = est_dans_2_ter(tmp, elem)\n",
    "        return res, cpt + cpt2        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "est_dans_2_ter([0, 0, 0, 0, 0], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "est_dans_2_ter([0, 0, 0, 0, 1], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "est_dans_2_ter([0]*1000, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Troisième essai : avec `pop(0)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def est_dans_v3(lst, elem):\n",
    "    if len(lst) == 0:\n",
    "        return False \n",
    "    premier = lst.pop(0)\n",
    "    if premier == elem:\n",
    "        return True\n",
    "    else:\n",
    "        return est_dans_v3(lst, elem)\n",
    "\n",
    "lst = [1, 2, 3]\n",
    "print(est_dans_v3(lst, 3))\n",
    "print(lst)\n",
    "print(est_dans_v3(lst, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "*Avantage :* une seule copie, mais... \n",
    "- détruit la liste !\n",
    "- toujours inefficace ! (`pop(0)` décale toute la liste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Quatrième essai : avec `pop()`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def est_dans_v4(lst, elem):\n",
    "    if len(lst) == 0:\n",
    "        return False \n",
    "    dernier = lst.pop()\n",
    "    if dernier == elem:\n",
    "        return True\n",
    "    else:\n",
    "        return est_dans_v4(lst, elem)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "lst = ['a', 'b', 'c']\n",
    "est_dans_v4(lst, 'b')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "est_dans_v4(lst, 'b')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "-   Parcourt la liste depuis la fin \n",
    "-   Plus efficace, mais... détruit toujours la liste !  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Cinquième essai : avec un indice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def est_dans_v5(lst, elem, indice):\n",
    "    if indice >= len(lst):\n",
    "        return False\n",
    "    elif lst[indice] == elem:\n",
    "        return True\n",
    "    else:\n",
    "        return est_dans_v5(lst, elem, indice+1)  \n",
    "    \n",
    "lst = ['a', 'b', 'c']\n",
    "est_dans_v5(lst, 'b', 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- Avantage : travaille toujours sur la même liste\n",
    "- Défaut : change la signature de la fonction (3 paramètres)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Sixième essai : avec un paramètre par défaut"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def est_dans_v6(lst, elem, indice=0):\n",
    "    if indice >= len(lst):\n",
    "        return False\n",
    "    elif lst[indice] == elem:\n",
    "        return True\n",
    "    else:\n",
    "        return est_dans_v6(lst, elem, indice+1)\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "lst = ['a', 'b', 'c']\n",
    "est_dans_v6(lst, 'd')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "-   Avantage : travaille toujours sur la même liste\n",
    "-   Valeur par défaut de `indice` si absent (`indice=0`)\n",
    "-   Appel sans le troisième argument : cherche sur toute la liste"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Une dernière forme : avec une fonction interne"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def est_dans_v7(lst, elem):\n",
    "\n",
    "    # fonction auxiliaire récursive!\n",
    "    def aux(indice):  \n",
    "        if indice >= len(lst):\n",
    "            return False\n",
    "        elif lst[indice] == elem:\n",
    "            return True\n",
    "        else:\n",
    "            return aux(indice + 1)\n",
    "\n",
    "    return aux(0)\n",
    "\n",
    "lst = ['a', 'b', 'c']\n",
    "est_dans_v7(lst, 'c')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**On compare !**\n",
    "\n",
    "Pour voir un peu comment ces fonctions se comportent en pratique, on va les chronométrer avec `timeit` sur des entrées de la forme `[0] * n`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "n = 20000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "setrecursionlimit(2*n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "%timeit est_dans_v2([0] * n, 1)\n",
    "%timeit est_dans_v3([0] * n, 1)\n",
    "%timeit est_dans_v6([0] * n, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Test de doublement :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "n = 10000\n",
    "%timeit est_dans_v3([0] * n, 1)\n",
    "%timeit est_dans_v3([0] * (n*2), 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "Le temps n'est pas *du tout* proportionnel à la taille de l'entrée !\n",
    "\n",
    "Logique : si $n (n-1) / 2 = x$, combien vaut $(2n) (2n-1) / 2$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "n = 10000\n",
    "%timeit est_dans_v6([0] * n, 1)\n",
    "%timeit est_dans_v6([0] * (n*2), 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "Le temps est *à peu près* proportionnel à la taille de l'entrée !"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.6"
  },
  "vscode": {
   "interpreter": {
    "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}