# AP1 · 4 — Raisonner par récursion

## Notre question

Comment compter une liste en ramenant le problème à une liste plus courte ?

> **Repères.** [Slides 49 à 55](https://ap-2026.noce.fr/slides/AP1-reference.html#49) : cas de base, appel sur le reste, pile d'appels. Poly, chap. 4 § « La récursion ». Le [poly](https://ap-2026.noce.fr/poly/poly-elixir.pdf)
> reprend ces notions par écrit.

Cet atelier de réserve est autonome : aucune cellule d'un autre notebook
n'est nécessaire. Le parcours principal de la séance est la série de
carnets `ap1-01-expressions.livemd` à `ap1-05-pile-calculatrice.livemd` ;
utilisez cette fiche pour reprendre une notion ou vous entraîner
davantage, selon les indications données en cours.
Nous utilisons le moteur Elixir de Livebook ; l'installation d'Elixir
sur votre système attendra AP6.

Commencez par prévoir le résultat, puis évaluez les cellules de haut en bas.
Écrivez les fonctions demandées dans la cellule indiquée. Gardez une phrase
sur une hésitation ou une découverte dans votre carnet principal.

> 💡 Pour démarrer : Le motif `[head | rest]` sépare une liste non vide en sa tête et son reste. `[]` est un cas distinct. L'appel sur `rest` traite un problème plus petit ; il faut encore prévoir ce qu'on fera de son résultat.

> 💡 Nous préciserons en cours les ateliers à terminer selon notre rythme.
> Les rubriques « Pour aller plus loin » restent facultatives.
> Vos réponses serviront au bilan, sans exercice supplémentaire à inventer.

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

## Retirer la tête (2 min)

Le motif `[head | rest]` sépare un élément de la liste qui suit.
Prévoyez ce que nous obtenons, puis remplacez la liste par `[4]`.
Pourquoi le même motif ne peut-il pas reconnaître `[]` ?

```elixir
[head | rest] = [4, 7, 2]
{head, rest}
```

## Compter par récurrence (5 min)

La liste vide a zéro élément. Une liste non vide contient sa tête, puis
les éléments du reste. Nous comptons donc 1, plus le résultat du même
problème sur `rest`. Écrivez la clause manquante de `ListWalk.count/1`,
sans utiliser `length/1` ni `Enum`.

La tête n'intervient pas dans le calcul : nommez-la `_head` pour le signaler.
L'underscore fait taire l'avertissement sur une valeur volontairement ignorée.

```elixir
defmodule ListWalk do
  def count([]), do: 0
  # Écrivez la clause pour une liste non vide.
end
```

Les exemples suivants sont des *doctests* : une entrée `iex>` suivie du
résultat attendu. Ils restent du texte dans Livebook ; les `assert`
juste en dessous vérifient le même contrat sans configuration à ajouter.

```text
iex> ListWalk.count([])
0

iex> ListWalk.count([:ok, "bonjour", 9])
3
```

```elixir
assert ListWalk.count([]) == 0
assert ListWalk.count([4]) == 1
assert ListWalk.count([:ok, "bonjour", 9]) == 3
```

## Voir les appels en attente (3 min)

Complétez cette trace dans une cellule de texte, jusqu'au résultat final :

```text
count([4, 7]) = 1 + count([7])
             = 1 + …
             = …
```

Au moment où nous atteignons `count([])`, combien d'additions attendent
encore leur résultat ? Qu'est-ce qui diminue à chaque appel ? Que se
passerait-il si nous rappelions la fonction sur la liste entière ?

Pour aller plus loin, ajoutez `sum/1` pour additionner une liste de nombres.
La structure est la même : quel élément faut-il ajouter au résultat du reste ?

## Garder une trace

Sauvegardez ce notebook dans `entrainement/ap1-recursion.livemd`,
en dehors du dossier collecté `AP1/`. Retrouvez la notion suivante dans
`ap1-accumulateurs.livemd` si vous souhaitez poursuivre cet entraînement.
Le parcours principal reste la série `AP1/ap1-01-expressions.livemd`
à `AP1/ap1-05-pile-calculatrice.livemd`, où vous conservez directement
le travail demandé pour le rendu unique du cycle AP1–AP3, le
6 décembre 2026 à 23 h 59 (Paris). Il n'y a pas de deuxième série
de notebooks à rendre.

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