{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6d262bd5",
   "metadata": {},
   "source": [
    "# Séance 2\n",
    "\n",
    "\n",
    "```{admonition} Objectifs\n",
    "* Listes\n",
    "* Boucles\n",
    "* Compléments sur les fonctions\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Listes\n",
    "\n",
    "### Création et accès\n",
    "\n",
    "Les **listes** sont des **structures de données** permettant de stocker différentes valeurs dans un ordre précis. Une liste est représentée par des crochets `[`, `]` entre lequels on place des éléments séparés par des virgules. Les éléments d'une même liste peuvent être de différentes natures : cela peut être des entiers, des flottants, des chaînes de caractères, et même d'autres listes.\n",
    "\n",
    "\n",
    "**Question.** Créer la liste des cinq premières lettres de l'alphabet, et l'affecter à la variable `L`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dca8874e",
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [\"a\", \"b\", \"c\", \"d\", \"e\"]\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55094e00",
   "metadata": {},
   "source": [
    "En python, le premier élément d'une liste a pour indice $0$. Si une liste contient $n$ éléments, le dernier élément a donc pour indice $n-1$. Par ailleurs, on accède à l'élément d'indice $i$ d'une liste `L` par `L[i]`.\n",
    "\n",
    "\n",
    "\n",
    "**Question.** Afficher le premier élément de la liste `L`, puis l'élément d'indice $3$ de la liste `L`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5bf3b8bb",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(L[0])\n",
    "print(L[3])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6382ce08",
   "metadata": {},
   "source": [
    "Attention à ne pas essayer d'accéder à un élément qui n'existe pas !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "be1c20a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "L[5]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dcc8cbcc",
   "metadata": {},
   "source": [
    "Dans le message d'erreur, python nous explique le problème : \"erreur d'indice : indice de liste hors de portée\". **En général, lisez bien les messages d'erreur, il vous renseignent sur le problème !**\n",
    "\n",
    "\n",
    "Pour ne pas se tromper sur le dernier élément, la fonction `len` permet de retourner la longueur d'une liste :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "35954474",
   "metadata": {},
   "outputs": [],
   "source": [
    "len(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5a16e81",
   "metadata": {},
   "source": [
    "**Remarque.** Il existe également une liste vide, représentée par `[]`. Sa longueur est nulle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "57722b00",
   "metadata": {},
   "outputs": [],
   "source": [
    "len([])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23d58ef3",
   "metadata": {},
   "source": [
    "Comme pour les chaînes de caractères, on peut concaténer deux listes avec l'opération `+`, et répéter plusieurs fois la même liste avec l'opération `*`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e84c3c67",
   "metadata": {},
   "outputs": [],
   "source": [
    "M = [1, 2]\n",
    "print(L + M)\n",
    "print(M * 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36e7152b",
   "metadata": {},
   "source": [
    "### Modification, suppression et insertion\n",
    "\n",
    "\n",
    "On peut également **modifier** le contenu d'une liste préexistante, par exemple en remplaçant la valeur `L[i]` stockée à un certain indice `i` par une autre valeur `v`. Pour cela, on affecte simplement la valeur à la \"case mémoire\" : on écrit `L[i] = v`. \n",
    "\n",
    "**Question.** Remplacer le $2$-ème élément de la liste `L` par l'entier $0$, puis afficher `L`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d80d1ba0",
   "metadata": {},
   "outputs": [],
   "source": [
    "L[1] = 0\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d405dced",
   "metadata": {},
   "source": [
    "Pour ajouter un élément en fin de liste, on peut utiliser la **méthode** de liste nommée `append`. Une **méthode** est une fonction attachée à un objet. On y accède par un point `.` qui sépare l'objet (avant) et la méthode (après). Généralement, on écrit donc\n",
    "```\n",
    "<objet>.<methode>(<arguments>)\n",
    "```\n",
    "\n",
    "Ainsi, pour ajouter la chaîne de caractères \"nouveau\" à la fin de la liste `L`, on écrit :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "addd7cb2",
   "metadata": {},
   "outputs": [],
   "source": [
    "L.append(\"nouveau\")\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d676b5a2",
   "metadata": {},
   "source": [
    "**Remarque.** La méthode `append` n'a **pas de valeur de retour**. Elle ne fait que modifier la liste `L`. Ainsi, on **n'écrira pas** `L = L.append(x)`.\n",
    "\n",
    "Pour **retirer** le dernier élément d'une liste, on utilise la méthode `pop`. Cette méthode modifie la liste, et a comme valeur de retour la valeur retirée.\n",
    "\n",
    "\n",
    "**Question.** Retirer le dernier élément de la liste `L` et le stocker dans `x`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3209cb39",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = L.pop()\n",
    "print(x)\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b2c41450",
   "metadata": {},
   "source": [
    "La méthode `pop` peut être utilisée pour retirer de la liste un élément d'indice quelconque. Pour cela, on place cet indice `i` comme argument de la méthode : on écrit `L.pop(i)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "56b6a56b",
   "metadata": {},
   "outputs": [],
   "source": [
    "M = [1, 2, 3]\n",
    "x = M.pop(1)\n",
    "print(M)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67a072c3",
   "metadata": {},
   "source": [
    "**Remarque.** La méthode `pop` peut donc être utilisée avec ou sans argument ; on parle d'argument **optionnel**.\n",
    "\n",
    "\n",
    "\n",
    "Il est également possible d'insérer des éléments dans une liste, à une position particulière. La méthode correspondante est `insert`. Elle prend en entrée deux arguments :\n",
    "* la position d'insertion (nommons-la `position`), qui est un entier entre $0$ et la longueur de la liste ;\n",
    "* la valeur à insérer (nommons-la `valeur`) qui est un élément quelconque.\n",
    "Pour un liste `L`, la syntaxe pour l'insertion est alors `L.insert(position, valeur)`.\n",
    "\n",
    "\n",
    "**Question.** Insérer le mot \"insertion\" en troisième position de la liste `L`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "31867f55",
   "metadata": {},
   "outputs": [],
   "source": [
    "L.insert(2, \"insertion\")\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d34c426d",
   "metadata": {},
   "source": [
    "Tableau récapitulatif. \n",
    "\n",
    "| Opération sur la liste | Syntaxe python |\n",
    "| :---: | :---: |\n",
    "| Longueur | `len(liste)` |\n",
    "| Concaténation | `liste_1 + liste_2` |\n",
    "| Accès à l'élément d'indice $i$ | `liste[i]` |\n",
    "| Modification à la position $i$ | `liste[i] = valeur` |\n",
    "| Ajout en fin de liste | `liste.append(valeur)` |\n",
    "| Insertion à la position $i$ | `liste.insert(i, v)` |\n",
    "| Suppression et accès (première position) | `valeur = liste.pop()` |\n",
    "| Suppression et accès (position générale)  | `valeur = liste.pop(i)` |\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Boucles\n",
    "\n",
    "Python permet de créer des **boucles,** c'est-à-dire une succession d'instructions à répéter. La répétition de ces instructions peut être paramètrée par une valeur ou par un test.\n",
    "\n",
    "Il existe deux formes principales de boucles : \n",
    "* les boucles `for`, qui permettent d'effectuer la série d'instructions **pour** certaines valeurs\n",
    "* et les boucles `while`, qui permettent d'effectuer la série d'instructions **tant qu'** une certaine condition est vérifiée. \n",
    "Dans les deux cas, les instructions à répéter **doivent être indentées** (utiliser la touche \"TAB\").\n",
    "\n",
    "\n",
    "### Boucle `for`\n",
    "\n",
    "Pour la boucle `for`, on utilise la syntaxe\n",
    "```\n",
    "for <variable> in <structure>:\n",
    "    <instruction1>\n",
    "    <instruction2>\n",
    "    <instruction3>\n",
    "```\n",
    "où `<structure>` peut-être, par exemple, une liste, une chaîne de caractères ou généralement un objet qu'on qualifie d'**itérable** (nous verrons cela par la suite). La variable `<variable>` est créée lors de l'initialisation de la boucle, et prend successivement comme valeur celle des éléments de `<structure>`. Attention : si la variable existe déjà, sa valeur antérieure sera écrasée !\n",
    "\n",
    "\n",
    "**Questions.** Déclarer une liste `L` contenant les chaînes de caractères associées aux lettres \"a\", \"b\" et \"c\". Puis, avec une boucle ``for``, afficher successivement les éléments de cette liste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e0aaac3c",
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [\"a\", \"b\", \"c\"]\n",
    "for x in L:\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84e299e8",
   "metadata": {},
   "source": [
    "**Question.** Avec une boucle `for` et une liste judicieusement créée, faire la somme des entiers de $2$ à $6$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "632192d6",
   "metadata": {},
   "outputs": [],
   "source": [
    "somme = 0\n",
    "for i in [2, 3, 4, 5, 6]:\n",
    "    somme = somme + i\n",
    "print(somme)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "557b18ba",
   "metadata": {},
   "source": [
    "Si l'on souhaitait faire la somme des entiers de $2$ à $10000$, on ne voudrait pas avoir à créer à la main la liste `[2, 3, 4, ..., 10000]`. Pour nous aider, le mot-clef `range` permet de décrire une suite arithmétique entière sous la forme d'un itérateur (ce n'est pas vraiment une liste). Ce mot-clef est particulièrement utile lorsqu'on souhaite parcourir tous les entiers entre `a` (inclus) et `b` (non-inclus). Pour cela, on écrit `range(a, b)`.\n",
    "\n",
    "**Question.** Même question que la précédente, mais sans la liste, et avec le mot-clef `range`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8b3f3cf4",
   "metadata": {},
   "outputs": [],
   "source": [
    "somme = 0\n",
    "for i in range(2,7):\n",
    "    somme += i\n",
    "somme"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7dbf12a",
   "metadata": {},
   "source": [
    "Si le premier paramètre `a` vaut $0$, alors on peut l'omettre et écrire plus simplement `range(b)`.\n",
    "\n",
    "**Question.** Même question en partant de l'entier $0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2ef70589",
   "metadata": {},
   "outputs": [],
   "source": [
    "somme = 0\n",
    "for i in range(7):\n",
    "    somme += i\n",
    "somme"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f36222aa",
   "metadata": {},
   "source": [
    "Le mot-clef `range` permet aussi de décrire les éléments d'une **suite arithmétique d'entiers**. Dans sa forme la plus générale, `range` prend ainsi comme paramètres trois entiers relatifs `a`, `b` et `c`. Dans ce cas, `range(a, b, c)` retourne la séquence d'entiers : $a$, $a+c$, $a+2c$, ..., $a +ic$, où $a+ic$ est le dernier terme de la suite qui n'atteint pas la valeur $b$. Par exemple, `range(-1, 7, 2)` parcourt les éléments $-1$, $1$, $3$ et $5$, tandis que `range(6, 2, -1)` parcourt les éléments $6$, $5$, $4$ et $3$.\n",
    "\n",
    "Lorsque `c` vaut $1$, on peut simplement écrire `range(a, b)`, et lorsque `c` vaut $1$ et `a` vaut $0$, on peut écrire `range(b)`.\n",
    "\n",
    "Un autre exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "33b0722f",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(-4, 8, 3):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c1b1dca",
   "metadata": {},
   "source": [
    "### Boucle `while`\n",
    "\n",
    "Une boucle `while` a la syntaxe suivante :\n",
    "```\n",
    "while <valeur_booleenne>:\n",
    "    <instruction1>\n",
    "    <instruction2>\n",
    "    <instruction3>\n",
    "```\n",
    "où `<valeur_booleenne>` est, comme son nom l'indique, une valeur booléenne le plus souvent issue d'un test logique. Les instructions se répètent tant que la valeur booléenne est vraie. Attention : si cette valeur n'est jamais fausse, la boucle va être répétée à l'infini !\n",
    "\n",
    "\n",
    "**Question.** Reprendre les questions précédentes avec une boucle ``while``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d6ef38d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [\"a\", \"b\", \"c\"]\n",
    "i = 0\n",
    "while (i < len(L)):\n",
    "    print(L[i])\n",
    "    i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "48908e4b",
   "metadata": {},
   "outputs": [],
   "source": [
    "somme = 0\n",
    "i = 2\n",
    "while (i < 7):\n",
    "    somme = somme + i\n",
    "    i += 1\n",
    "somme"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4e3f64c1",
   "metadata": {},
   "outputs": [],
   "source": [
    "somme = 0\n",
    "i = 0\n",
    "while (i < 7):\n",
    "    somme = somme + i\n",
    "    i += 1\n",
    "somme"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9129abb7",
   "metadata": {},
   "source": [
    "## Fonctions récursives\n",
    "\n",
    "\n",
    "Dans le chapitre précédent, nous avons vu comme créer des fonctions simples et comment les appeler. Les fonctions peuvent s'appeler elles-mêmes : on parle de fonction **récursive**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ca7fda5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def compte_a_rebours(n):\n",
    "    if (n == 0):\n",
    "        print(\"Départ\")\n",
    "    else:\n",
    "        print(n)\n",
    "        compte_a_rebours(n-1)\n",
    "        \n",
    "compte_a_rebours(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7b4925e",
   "metadata": {},
   "source": [
    "Il assez naturel d'utiliser des fonctions récursives pour implanter des calculs de nature récursive sur des objets. On peut penser par exemple au calcul du $n$-ème terme d'une suite récurrente simple.\n",
    "\n",
    "**Question.** Supposons que $(u_n)_n$ soit définie par $u_0 = 2$ et $u_n = n u_{n-1} - 3 (n-1)^2$ pour tout $n \\ge 0$. Écrire une fonction récursive `calcule_u(n)` qui calcule le terme d'ordre $n$ de la suite $(u_n)_n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "902a6382",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calcule_u(n):\n",
    "    if (n == 0):\n",
    "        return 2\n",
    "    else:\n",
    "        return n * calcule_u(n-1) - 3 * (n-1)**2\n",
    "        \n",
    "calcule_u(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f1454a0d",
   "metadata": {},
   "source": [
    "## Passage par valeur ou par adresse\n",
    "\n",
    "Lorsque l'on passe une variable comme argument d'une fonction, python réalise une copie \"locale\" de la variable qui sera utilisée lors du temps de l'exécution de la fonction.\n",
    "\n",
    "Ainsi, lorsqu'un entier passé en paramètre d'une fonction est modifié, on a le comportement suivant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ee0db1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def carre(n):\n",
    "    n = n**2\n",
    "    print(\"Dans  l'appel de fonction, n =\", n)\n",
    "    return n\n",
    "    \n",
    "n = 2\n",
    "print(\"Avant l'appel de fonction, n =\", n)\n",
    "c = carre(n)\n",
    "print(\"Après l'appel de fonction, n =\", n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7de619a8",
   "metadata": {},
   "source": [
    "C'est donc la copie de `n`, interne à la fonction `carre`, qui est modifiée. On parle de **passage par valeur** du paramètre de la fonction.\n",
    "\n",
    "\n",
    "\n",
    "Si le paramètre de la fonction est une liste, le comportement est différent. En effet, une liste est définie par une adresse mémoire qui \"pointe\" vers des données (les éléments de la liste). Lors de l'appel de la fonction, la copie de l'adresse mémoire de la liste donne donc accès aux mêmes éléments que la liste initiale. Toute modification de la liste dans la fonction s'observera donc hors de la fonction. On parle de **passage** du paramètre **par adresse**. Voici un comportement typique :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ea5d2676",
   "metadata": {},
   "outputs": [],
   "source": [
    "def avant_dernier_element(L):\n",
    "    L.pop()\n",
    "    x = L.pop()\n",
    "    print(\"Dans  l'appel de fonction, L =\", L)\n",
    "    return x\n",
    "\n",
    "L = [1, 2, 3, 4, 5]\n",
    "print(\"Avant l'appel de fonction, L =\", L)\n",
    "x = avant_dernier_element(L)\n",
    "print(\"Après l'appel de fonction, L =\", L)\n",
    "print(\"Avant-dernier élément :\", x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a52d4a17",
   "metadata": {},
   "source": [
    "```{warning} \n",
    "Attention, réaffecter la liste à une autre variable ne résout pas le problème ! En effet, l'affectation `M = L` ne fait que copier l'adresse mémoire de la liste `L` dans la variable `M`. Pour faire une copie \"dure\" de la liste, il faut utiliser `M = L.copy()` \n",
    "```"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}