# AP1 · 3 — Parcourir une liste en sachant où nous en sommes ## Notre question Comment parcourir une liste sans boucle `for`, et comment savoir où nous en sommes ? Une fonction récursive traite la tête et rappelle la fonction sur le reste ; un accumulateur transporte le travail déjà fait. > **Repères.** Poly, chap. 3, section 3.2 « La liste », et chap. 4, section 4.4 « La récursion ». Le cours se fait ici, dans le carnet. > 💡 Durée indicative : 25 min, reprise collective comprise. Ce carnet > est autonome : aucune cellule d'un autre carnet n'est nécessaire. Je le > projette au tableau ; écrivez une prédiction avant d'exécuter, puis > expliquez un résultat qui vous a surpris. **Sauvegardez-le dès maintenant > sous `AP1/ap1-03-listes-recursion.livemd`.** Les cellules `assert` sont des vérifications fournies : si une condition est fausse, Livebook montre le résultat obtenu et celui attendu. Évaluez cet import une fois, puis réévaluez votre code avant ses tests après chaque modification. ```elixir import ExUnit.Assertions ``` ## Décomposer une liste Les crochets construisent une liste : `[4, 7, 9]`. Contrairement à un tableau NumPy, une liste Elixir est chaînée : la tête est suivie d'une autre liste. `[head | rest]` reconnaît précisément cette structure. `[]` est le cas vide. Prévoyez ce que donne chaque élément du tuple. ```elixir values = [4, 7, 9] [head | rest] = values {[0 | values], head, rest, values} ``` `[0 | values]` crée une nouvelle liste et conserve l'ancienne. Pour retirer la tête, nous utilisons `rest` ; aucune méthode `pop` ne modifie la liste en place. Une liste permet de retrouver efficacement sa tête, pas d'accéder à n'importe quel indice comme un tableau. Le comptage donne un premier exemple de *solution par récurrence* : la liste vide contient zéro élément ; une liste non vide contient un élément de plus que son reste. Traduisez chaque ligne en français. ```elixir defmodule ListWalk do def count([]), do: 0 def count([_head | rest]), do: 1 + count(rest) end ``` ```elixir assert ListWalk.count([]) == 0 assert ListWalk.count([4, 7, 9]) == 3 ``` Pour `count([4, 7])`, nous devons encore ajouter 1 après avoir calculé `count([7])`, qui doit lui-même ajouter 1 après `count([])`. Il reste donc du travail au retour des appels. ## B1 — Transporter le travail déjà fait Un *accumulateur* reçoit l'état déjà calculé. Écrivez `Tally.count/2` : `count(values, total)` renvoie le nombre d'éléments de `values` ajouté à `total`. Traitez les cas vide et non vide par deux clauses. Dans le second, passez directement le compteur mis à jour à l'appel récursif. ```elixir defmodule Tally do # Écrivez les deux clauses de count/2. end ``` ```elixir assert Tally.count([], 5) == 5 assert Tally.count([4, 7], 10) == 12 assert Tally.count([:a, :b, :c], 0) == 3 ``` Tracez les couples `(reste, compteur)` pour `Tally.count([4, 7], 10)`. Quelle quantité diminue ? Que représente le compteur à chaque appel ? Ici, le compteur est mis à jour avant l'appel suivant. Il ne reste rien à faire après son retour : c'est un *appel terminal*. Quand les appels récursifs sont terminaux, on parle de *récursion terminale*. La BEAM peut alors poursuivre sans empiler un travail en attente pour chaque élément. Cette boucle garde une profondeur de pile d'appels constante, comme une boucle `while`. Pour construire une liste au fil d'une lecture, nous pourrons aussi transporter une liste comme accumulateur. Ajouter en tête est simple ; il faut alors remettre les éléments dans l'ordre à la fin. `Enum.reverse/1` est la fonction fournie pour cela ; elle ne modifie pas son argument. ```elixir reversed = [] reversed = [1 | reversed] reversed = [2 | reversed] reversed = [3 | reversed] {reversed, Enum.reverse(reversed)} ``` **Transfert.** Sans recopier le compteur, écrivez `ListTotal.sum/1` qui additionne les nombres d'une liste. À vous de choisir les clauses et de dire si votre version a besoin d'un accumulateur. Ajoutez une assertion qui distingue votre fonction d'un simple comptage. ```elixir defmodule ListTotal do # Écrivez sum/1, puis choisissez un cas personnel. end ``` ```elixir assert ListTotal.sum([]) == 0 assert ListTotal.sum([4, 7]) == 11 ``` ## Reconnaître un appel terminal Après votre essai, comparons deux sommes. Prévoyez les trois résultats avant d'évaluer. Dans `head + sum(rest)` et `sum(rest, acc + head)`, l'addition a-t-elle lieu avant ou après l'appel récursif ? Laquelle des deux fonctions est terminale ? ```elixir defmodule Totals do def sum([]), do: 0 def sum([head | rest]), do: head + sum(rest) def sum([], acc), do: acc def sum([head | rest], acc), do: sum(rest, acc + head) end {Totals.sum([2, 3]), Totals.sum([2, 3], 0), Totals.sum([2, 3], 10)} ``` ```elixir assert Totals.sum([2, 3]) == 5 assert Totals.sum([2, 3], 0) == 5 assert Totals.sum([2, 3], 10) == 15 assert Totals.sum([], 10) == 10 ``` Tracez les états `(reste, acc)` du deuxième appel, puis comparez avec le schéma de la pile d'appels du poly, chapitre 4, section 4.4. Une pile d'appels constante ne signifie pas que toutes les données occupent une mémoire constante : une liste accumulée peut grandir, un entier aussi. La terminaison est encore une autre question. Ici, une liste finie raccourcit jusqu'à `[]`. Une fonction qui rappellerait directement `loop(state)` avec le même état aurait-elle un appel terminal ? Pour autant, s'arrêterait-elle ? Expliquez sans l'exécuter. Il faut savoir reconnaître cette forme dès AP1 ; il n'est pas demandé de réécrire toutes vos fonctions avec un accumulateur. Une somme exprimée par `head + sum(rest)` reste une solution correcte. ## Garder une trace Conservez la trace `(reste, acc)` que vous avez écrite et une phrase qui distingue trois questions : quel résultat, quel travail reste en attente après l'appel, qu'est-ce qui rapproche du cas d'arrêt. Enregistrez ce carnet sous `AP1/ap1-03-listes-recursion.livemd` dans votre dépôt privé `ap-homework`, puis ouvrez `ap1-04-chaines-tokens.livemd` depuis la page AP1 quand nous y passons ensemble. Chaque carnet repart d'une session neuve : vos modules précédents ne sont pas chargés, et ce n'est pas nécessaire. Un bout de syntaxe oublié ? Les chapitres 1 à 4 du [poly](https://ap-2026.noce.fr/poly/poly-elixir.pdf) reprennent les formes du langage, chacune avec un exemple et son résultat ; le cours, lui, se fait dans les carnets. Pour toute question, vous pouvez me contacter par email : [aurelien.noce@minesparis.psl.eu](mailto:aurelien.noce@minesparis.psl.eu).