# TP optionnel — De la récursion naïve à la programmation dynamique

## Comment travailler ce notebook

> **Optionnel, non noté — prenez votre temps.**
> Ce TP est un bonus, rattaché à la **séance 3** (récursion, `Enum`, `Stream`).
> Il n'entre dans aucune note. Il est là pour celles et ceux que le sujet
> démange : à faire à la maison, en fin de séance, ou un soir de pluie. Il est
> **long** — plusieurs heures de matière, difficulté croissante. C'est voulu.
> N'essayez pas de tout finir d'un coup ; avancez case par case, quittez quand
> vous voulez, revenez plus tard. Le dernier exercice est délibérément ouvert :
> personne n'est censé « terminer » ce notebook.

Ce notebook tourne sur la vraie machine virtuelle d'Elixir, la **BEAM**. Tout
se fait avec la **bibliothèque standard** — aucune dépendance à installer.

**La règle du jeu :**

* Chaque section pose un problème. Vous trouverez une cellule de code avec un
  ou plusieurs trous marqués `# À COMPLÉTER (n)`. Remplacez-les par votre code,
  puis **évaluez** la cellule (**Ctrl/Cmd + Entrée**).
* Sous la plupart des exercices, une cellule de **vérification** vous attend.
  Elle affiche `✅` si tout va bien, ou **lève une erreur explicite** sinon. Ne
  la modifiez pas : elle est là pour vous, pas contre vous. Ces vérifications
  testent des **propriétés** (valeurs connues, invariants, tailles qui forcent
  la mémoïsation) — impossible de les satisfaire en trichant.
* Les cellules s'évaluent **de haut en bas**. En cas de doute, menu du notebook
  → *Evaluate all*.
* Il n'y a **aucun corrigé** ici. Plutôt que de chercher « la » réponse,
  demandez-vous à chaque étape « comment je sais que ça marche ? ».

Le fil rouge : une récursion naïve qui **explose**, qu'on apprend d'abord à
**mesurer**, puis à sauver par la **mémoïsation** (*memoization*), et enfin à
généraliser en **programmation dynamique** (*dynamic programming*). Un point de
vigilance Elixir, à garder en tête tout du long : comme rien n'est mutable ici,
mémoïser ne consiste **pas** à écrire dans un dictionnaire partagé comme en
Python (`cache[n] = v`), mais à **faire circuler** une table de résultats déjà
connus entre les appels — elle est lue, complétée, puis **renvoyée** avec le
résultat. C'est exactement l'**accumulateur** de la séance 3, revu à la sauce
« cache ».

## Exercice 1 — Fibonacci naïf, et le mur qui arrive

La suite de Fibonacci : `fib(0) = 0`, `fib(1) = 1`, et `fib(n) = fib(n-1) +
fib(n-2)` pour `n ≥ 2`. La définition mathématique *est* la définition
récursive — écrivez-la telle quelle, sans ruse.

```elixir
defmodule FibNaif do
  # À COMPLÉTER (1) : les deux cas de base.
  # fib(0) vaut 0, fib(1) vaut 1.

  def fib(n) do
    # À COMPLÉTER (2) : le cas récursif, la définition mathématique
    # transcrite mot pour mot.
  end
end

# Un premier test à l'œil :
Enum.map(0..10, &FibNaif.fib/1)
```

Vérification :

```elixir
# fib(0..10) = 0,1,1,2,3,5,8,13,21,34,55 — les onze premiers termes, connus.
attendus = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
obtenus = Enum.map(0..10, &FibNaif.fib/1)

if obtenus != attendus do
  raise "fib(0..10) devrait valoir #{inspect(attendus)}, obtenu #{inspect(obtenus)}"
end

IO.puts("✅ Les onze premiers termes de Fibonacci sont corrects")
```

## Exercice 2 — Mesurer l'explosion

`FibNaif.fib/1` est correct. Est-il **utilisable** ? Mesurons-le. On chronomètre
avec `System.monotonic_time/1` : une horloge qui ne recule jamais, idéale pour
mesurer une durée (contrairement à l'heure murale, qui peut sauter).

Écrivez `chrono/1` : elle reçoit une fonction **sans argument** (une
*thunk*, `fn -> ... end`), l'exécute, et renvoie le tuple
`{resultat, duree_ms}` — la valeur produite **et** le temps écoulé en
millisecondes.

```elixir
defmodule Chrono do
  def mesurer(fun) do
    debut = System.monotonic_time(:millisecond)
    # À COMPLÉTER (1) : appelle `fun` (c'est `fun.()`) et retiens son résultat.
    resultat = nil
    fin = System.monotonic_time(:millisecond)
    # À COMPLÉTER (2) : renvoie {resultat, duree_en_ms}.
  end
end

# Faites monter `n` DOUCEMENT : 25, puis 30, puis 32, puis 35...
# Regardez la durée. Ne dépassez pas ~40, sous peine d'attendre longtemps.
n = 30
{valeur, ms} = Chrono.mesurer(fn -> FibNaif.fib(n) end)
IO.puts("fib(#{n}) = #{valeur} en #{ms} ms")
```

Vérification :

```elixir
# La mesure doit renvoyer la BONNE valeur, et une durée numérique >= 0.
{v, ms} = Chrono.mesurer(fn -> FibNaif.fib(20) end)

cond do
  v != 6765 -> raise "fib(20) devrait valoir 6765, obtenu #{inspect(v)}"
  not is_integer(ms) or ms < 0 -> raise "la durée devrait être un entier de ms >= 0, obtenu #{inspect(ms)}"
  true -> IO.puts("✅ Chrono renvoie {résultat, durée_ms} — fib(20) = #{v} en #{ms} ms")
end
```

> **Expliquez (dans une cellule Markdown à vous, ou sur papier).**
> Chaque incrément de `n` fait environ **doubler** le temps de calcul. Pourquoi ?
> Dessinez l'arbre des appels de `fib(5)` : combien de fois `fib(2)` y est-il
> calculé ? Et `fib(3)` ? Un même sous-problème est recalculé encore et encore —
> c'est **là** qu'est le gaspillage. Estimez : `fib(40)` demanderait combien de
> temps par rapport à `fib(30)` ? Et `fib(80)` (n'essayez pas de le lancer !) ?

## Exercice 3 — Compter les appels, chiffrer le gaspillage

L'exercice 2 vous a fait *sentir* l'explosion ; celui-ci va la **chiffrer**. On
veut savoir combien de fois `fib` est appelée en tout pour calculer `fib(n)`.

L'astuce Elixir : puisqu'on ne peut pas incrémenter un compteur mutable, on fait
**voyager le compteur** — c'est un accumulateur. Écrivez `compte/1` qui renvoie
`{valeur_de_fib, nombre_d_appels}` : chaque appel se compte lui-même (`1`) plus
les appels de ses enfants.

```elixir
defmodule FibCompte do
  # Renvoie {fib(n), nombre total d'appels à fib pour l'obtenir}.
  # Cas de base : fib(0) et fib(1) coûtent chacun 1 appel (celui-ci).
  def compte(0), do: {0, 1}
  def compte(1), do: {1, 1}

  def compte(n) do
    {v1, c1} = compte(n - 1)
    {v2, c2} = compte(n - 2)
    # À COMPLÉTER (1) : la valeur de fib(n) à partir de v1 et v2,
    # et le nombre d'appels = 1 (celui-ci) + c1 + c2.
    # Renvoie le tuple {valeur, total_appels}.
  end
end

Enum.map(0..15, fn n ->
  {v, c} = FibCompte.compte(n)
  {n, v, c}
end)
```

Vérification :

```elixir
# Propriétés : la valeur de fib doit rester correcte, et le nombre d'appels
# doit exploser (croissance exponentielle). On connaît quelques points exacts.
{v10, c10} = FibCompte.compte(10)
{v20, c20} = FibCompte.compte(20)

cond do
  v10 != 55 -> raise "fib(10) devrait valoir 55, obtenu #{v10}"
  v20 != 6765 -> raise "fib(20) devrait valoir 6765, obtenu #{v20}"
  c10 != 177 -> raise "fib(10) devrait coûter 177 appels, obtenu #{c10} (attention au comptage : chaque appel compte 1 + ses enfants)"
  c20 != 21891 -> raise "fib(20) devrait coûter 21891 appels, obtenu #{c20}"
  true -> IO.puts("✅ fib(10) = 55 en #{c10} appels ; fib(20) = 6765 en #{c20} appels. On mesure le gâchis.")
end
```

> **Pour aller plus loin (optionnel, teaser de la séance 4).**
> On aurait aussi pu compter avec un **process compteur** : un process qui
> garde un état (le nombre d'appels vus) et qu'on incrémente par message à
> chaque appel de `fib`. C'est exactement le « compteur » de la séance 4 (le
> modèle acteur). Ici, l'accumulateur voyageur suffit et reste plus simple —
> mais gardez en tête que *compter des événements* est un besoin qui reviendra,
> et qu'un état vivant dans un process en est une autre réponse.

## Exercice 4 — Mémoïser : le cache est un accumulateur

Voici le cœur du TP. Ce qui pose problème dans `fib` naïf, ce n'est pas la
récursion : c'est de recalculer sans cesse les mêmes sous-problèmes. La parade
consiste à garder dans une **table** (une `Map`) les valeurs déjà calculées,
et à la consulter avant de recalculer.

Attention au réflexe venu de Python : on n'a pas ici de dictionnaire global
qu'on modifie sur place, la map est **immuable**. Chaque fonction reçoit donc
le cache courant en argument et renvoie `{valeur, cache_mis_à_jour}`, le cache
enrichi ressortant pour servir aux appels suivants. En clair, le cache est un
accumulateur.

```elixir
defmodule FibMemo do
  # API publique : on démarre avec un cache vide et on ne rend que la valeur.
  def fib(n) do
    {valeur, _cache} = calc(n, %{})
    valeur
  end

  # Cas de base : la valeur est immédiate, le cache ressort inchangé.
  defp calc(0, cache), do: {0, cache}
  defp calc(1, cache), do: {1, cache}

  defp calc(n, cache) do
    case Map.get(cache, n) do
      nil ->
        # Pas encore connu : on calcule les deux sous-problèmes EN FAISANT
        # CIRCULER le cache. Le cache ressorti du 1er appel entre dans le 2e.
        {v1, cache1} = calc(n - 1, cache)
        # À COMPLÉTER (1) : calcule fib(n-2) en partant de `cache1`
        # (surtout pas de `cache` : on veut PROFITER de ce que cache1 a appris).
        {v2, cache2} = nil

        valeur = v1 + v2
        # À COMPLÉTER (2) : mémorise `valeur` sous la clé `n` dans cache2,
        # et renvoie {valeur, ce_nouveau_cache}.

      deja_connu ->
        # Déjà dans le cache : on le renvoie sans rien recalculer.
        {deja_connu, cache}
    end
  end
end

FibMemo.fib(10)
```

Vérification :

```elixir
# 1) Valeurs connues encore correctes.
attendus = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
if Enum.map(0..10, &FibMemo.fib/1) != attendus do
  raise "les 11 premiers termes ont changé : #{inspect(Enum.map(0..10, &FibMemo.fib/1))}"
end

# 2) LA propriété qui distingue la mémoïsation : fib(80) doit répondre
#    INSTANTANÉMENT. En naïf, ce serait des milliards de milliards d'appels.
{v80, ms} = Chrono.mesurer(fn -> FibMemo.fib(80) end)

cond do
  v80 != 23416728348467685 -> raise "fib(80) devrait valoir 23416728348467685, obtenu #{v80}"
  ms > 200 -> raise "fib(80) a pris #{ms} ms — trop lent, la mémoïsation ne fonctionne pas (le cache circule-t-il bien d'un appel au suivant ?)"
  true -> IO.puts("✅ fib(80) = #{v80} en #{ms} ms — instantané. La mémoïsation tient.")
end
```

> **Expliquez.** Comparez la ligne `{v2, cache2} = calc(n - 2, cache1)` à la
> variante fautive `{v2, cache2} = calc(n - 2, cache)`. Les deux donnent la
> **bonne valeur** de `fib`. Une seule est rapide. Laquelle, et pourquoi ?
> (Indice : qu'a appris `cache1` que `cache` ignore ?) C'est toute la subtilité
> de la mémoïsation en immuable : il ne suffit pas de *stocker*, il faut faire
> **remonter** le cache enrichi le long de toute la récursion.

## Exercice 5 — L'escalier : Fibonacci déguisé

On monte un escalier de `n` marches. À chaque pas, on monte **1** ou **2**
marches. Combien de façons distinctes d'arriver en haut ?

Petits cas à la main : pour `n = 3`, les chemins sont `1+1+1`, `1+2`, `2+1` →
**3 façons**. Pour `n = 4` : `1+1+1+1`, `1+1+2`, `1+2+1`, `2+1+1`, `2+2` →
**5 façons**.

Écrivez `facons/1`. Pensez récurrence : pour atteindre la marche `n`, le
**dernier** pas venait soit de la marche `n-1` (pas de 1), soit de la marche
`n-2` (pas de 2). Donc `facons(n) = facons(n-1) + facons(n-2)`.

```elixir
defmodule Escalier do
  # Combien de façons de monter n marches par pas de 1 ou 2 ?
  # À COMPLÉTER (1) : les cas de base.
  #   - 0 marche : il y a 1 façon (ne rien faire, on est déjà en haut).
  #   - 1 marche : 1 façon.

  def facons(n) do
    # À COMPLÉTER (2) : le cas récursif.
    # (Pour de grands n, réutilisez FibMemo ou mémoïsez : c'est le même moule.)
  end
end

Enum.map(0..6, &Escalier.facons/1)
```

Vérification :

```elixir
# facons(0..6) = 1,1,2,3,5,8,13 — c'est Fibonacci DÉCALÉ.
attendus = [1, 1, 2, 3, 5, 8, 13]
obtenus = Enum.map(0..6, &Escalier.facons/1)

cond do
  obtenus != attendus -> raise "facons(0..6) devrait valoir #{inspect(attendus)}, obtenu #{inspect(obtenus)}"
  Escalier.facons(4) != 5 -> raise "facons(4) devrait valoir 5"
  true -> IO.puts("✅ L'escalier : #{inspect(obtenus)}. Vous reconnaissez la suite ?")
end
```

> **Expliquez.** `facons(n)` vaut `fib(n+1)` (avec la convention `fib(0)=0`,
> `fib(1)=1`). Pourquoi cet **exact** décalage ? Comparez la relation de
> récurrence de l'escalier à celle de Fibonacci, **et** leurs cas de base.
> Deux problèmes qui n'ont rien à voir (des lapins, un escalier) partagent la
> même structure : c'est précisément ce que la programmation dynamique apprend
> à **reconnaître**.

## Exercice 6 — Le rendu de monnaie, et le piège du glouton

Nouveau problème, plus riche : avec un système de pièces `[p1, p2, ...]` (en
quantité illimitée), quel est le **nombre minimal** de pièces pour faire
exactement un montant `m` ?

L'idée « évidente » est l'algorithme **glouton** (*greedy*) : prendre à chaque
étape la plus grosse pièce qui rentre. Sur l'euro (`[1, 2, 5, 10, ...]`), il
donne toujours l'optimum, mais ce n'est pas vrai sur tous les systèmes de
pièces. On va vous le *faire constater*.

D'abord, la version glouton :

```elixir
defmodule MonnaieGlouton do
  # Rend `montant` avec le moins de pièces possible, façon glouton :
  # à chaque coup, la plus grosse pièce <= au reste.
  def rendre(pieces, montant) do
    triees = Enum.sort(pieces, :desc)
    rendre(triees, montant, 0)
  end

  defp rendre(_pieces, 0, n), do: n
  defp rendre([], _reste, _n), do: :impossible

  defp rendre([p | autres], reste, n) when p <= reste do
    # À COMPLÉTER (1) : on prend une pièce `p` (donc n augmente de 1),
    # le reste diminue de `p`, et on RESTE sur la même pièce `p`
    # (on peut en reprendre) → rappelle rendre([p | autres], reste - p, n + 1).
  end

  defp rendre([_p | autres], reste, n) do
    # `p` est trop grosse pour le reste : on passe à la pièce suivante.
    rendre(autres, reste, n)
  end
end

# L'euro, système "canonique" : le glouton est optimal.
MonnaieGlouton.rendre([1, 2, 5, 10, 20, 50], 63)
```

Vérification (du glouton seul) :

```elixir
cond do
  # 63 = 50 + 10 + 2 + 1 → 4 pièces (système euro, canonique).
  MonnaieGlouton.rendre([1, 2, 5, 10, 20, 50], 63) != 4 ->
    raise "rendre(euros, 63) devrait valoir 4 (50+10+2+1), obtenu #{inspect(MonnaieGlouton.rendre([1, 2, 5, 10, 20, 50], 63))}"
  MonnaieGlouton.rendre([1, 5, 10, 25], 30) != 2 ->
    raise "30 = 25 + 5 = 2 pièces (système US, canonique)"
  true -> IO.puts("✅ Le glouton marche sur les systèmes canoniques (euro, US)")
end
```

> **Le piège, à FAIRE CONSTATER.** Prenez le système `[1, 3, 4]` et le montant
> `6`. Le glouton prend `4`, puis il ne reste que des `1` : `4 + 1 + 1` = **3
> pièces**. Or `3 + 3` = **2 pièces** ! Le glouton s'est trompé. Évaluez la
> cellule ci-dessous et regardez la différence de vos propres yeux :

```elixir
resultat_glouton = MonnaieGlouton.rendre([1, 3, 4], 6)
IO.puts("Glouton sur [1,3,4] pour 6 : #{resultat_glouton} pièces (4+1+1)")
IO.puts("Optimum réel : 2 pièces (3+3)")
IO.puts("→ Le glouton n'est PAS optimal sur ce système. Il faut la prog. dynamique.")
```

Maintenant la **vraie** solution, par programmation dynamique. Pour rendre
`montant`, on essaie **chaque** pièce `p` en premier, et on garde le meilleur
choix : `1 + optimal(montant - p)`. On mémoïse pour ne pas recalculer
`optimal(reste)` mille fois.

```elixir
defmodule MonnaieDP do
  # Renvoie le nombre MINIMAL de pièces pour `montant`, ou :impossible.
  def rendre(pieces, montant) do
    {res, _cache} = calc(pieces, montant, %{})

    case res do
      :infini -> :impossible
      n -> n
    end
  end

  # On travaille avec :infini comme "pas de solution" pour pouvoir prendre des min.
  defp calc(_pieces, 0, cache), do: {0, cache}

  defp calc(pieces, montant, cache) do
    case Map.get(cache, montant) do
      nil ->
        # On essaie toutes les pièces qui "rentrent" et on garde le meilleur.
        {meilleur, cache_final} =
          Enum.reduce(pieces, {:infini, cache}, fn p, {best, c} ->
            if p <= montant do
              {sous, c2} = calc(pieces, montant - p, c)

              candidat =
                case sous do
                  :infini -> :infini
                  # À COMPLÉTER (1) : si le sous-problème coûte `sous` pièces,
                  # alors passer par `p` en coûte une de plus.
                  n -> nil
                end

              # À COMPLÉTER (2) : le nouveau "best" est le plus petit entre
              # `best` et `candidat`. Attention : :infini doit perdre contre
              # n'importe quel entier. Écrivez un min qui gère :infini.
              nouveau_best = nil
              {nouveau_best, c2}
            else
              {best, c}
            end
          end)

        {meilleur, Map.put(cache_final, montant, meilleur)}

      deja_connu ->
        {deja_connu, cache}
    end
  end
end

MonnaieDP.rendre([1, 3, 4], 6)
```

Vérification :

```elixir
cond do
  # LE cas qui piège le glouton : la DP doit trouver 2 (3+3), pas 3.
  MonnaieDP.rendre([1, 3, 4], 6) != 2 ->
    raise "rendre([1,3,4], 6) devrait valoir 2 (3+3), obtenu #{inspect(MonnaieDP.rendre([1, 3, 4], 6))} — le glouton se trompe ici, pas la DP !"

  # Systèmes canoniques : la DP donne le même optimum que le glouton.
  MonnaieDP.rendre([1, 2, 5, 10, 20, 50], 63) != 4 ->
    raise "rendre(euros, 63) devrait valoir 4 (50+10+2+1)"

  # Montant 0 : zéro pièce.
  MonnaieDP.rendre([1, 3, 4], 0) != 0 ->
    raise "rendre(_, 0) devrait valoir 0"

  # Impossible : avec seulement des pièces de 2, on ne fait pas 3.
  MonnaieDP.rendre([2], 3) != :impossible ->
    raise "rendre([2], 3) devrait être :impossible"

  # Un plus gros, pour forcer la mémoïsation (sans cache, ce serait très lent).
  MonnaieDP.rendre([1, 3, 4], 100) != 25 ->
    raise "rendre([1,3,4], 100) devrait valoir 25 (25 pièces de 4)"

  true ->
    IO.puts("✅ La DP bat le glouton sur [1,3,4]/6, égale l'euro, gère l'impossible et le montant 0.")
end
```

> **Expliquez.** (a) Pourquoi la DP trouve-t-elle `3+3` alors que le glouton ne
> le voit pas ? Qu'est-ce que « essayer toutes les pièces en premier » apporte
> que « prendre la plus grosse » n'a pas ? (b) Sans le cache, combien de fois
> `calc(pieces, 50, _)` serait-il évalué en calculant `rendre([1,3,4], 100)` ?
> C'est le même gaspillage qu'au Fibonacci naïf — **exactement** le même.

## Exercice 7 (ouvert) — Sac à dos, ou plus longue sous-séquence commune

Vous tenez maintenant le moule complet de la programmation dynamique :
**décomposer** en sous-problèmes qui se recouvrent, **mémoïser** en faisant
circuler un cache immuable. Choisissez **un** des deux problèmes ci-dessous (ou
les deux, si le démon vous tient) et écrivez-le **de zéro**, sans squelette.

Il n'y a **pas** de vérification fournie : c'est à vous d'écrire vos propres
tests par propriétés, sur le modèle des cellules précédentes. Savoir *décider si
son code est correct* fait partie de l'exercice — c'est même le plus important.

**Option A — Le sac à dos 0/1 (*knapsack*).** On a `n` objets, chacun avec un
poids et une valeur, et un sac de capacité `C`. On veut **maximiser** la valeur
totale des objets emportés sans dépasser `C`, chaque objet étant pris **ou pas**
(pas de fraction, pas de doublon). Récurrence : pour l'objet `i` face à la
capacité restante `c`, le meilleur est le **max** entre « je ne le prends pas »
(`sac(i+1, c)`) et, si `poids_i ≤ c`, « je le prends » (`valeur_i +
sac(i+1, c - poids_i)`). L'état à mémoïser est le couple `{i, c}`.

*Points d'appui pour vos tests :* objets `[{poids: 1, val: 1}, {poids: 3, val:
4}, {poids: 4, val: 5}, {poids: 5, val: 7}]` avec `C = 7` → valeur optimale
**9** (les objets de poids 3 et 4). Capacité 0 → valeur 0. Un seul objet plus
lourd que le sac → valeur 0.

**Option B — La plus longue sous-séquence commune (*LCS*).** Une *sous-séquence*
garde l'ordre mais pas forcément la contiguïté (`"ace"` est une sous-séquence de
`"abcde"`). Étant données deux chaînes (ou listes) `a` et `b`, quelle est la
**longueur** de leur plus longue sous-séquence commune ? Récurrence sur les deux
premières têtes : si `tête(a) == tête(b)`, alors `1 + lcs(reste(a), reste(b))` ;
sinon, le **max** entre `lcs(reste(a), b)` et `lcs(a, reste(b))`. Cas de base :
si l'une des deux est vide, la LCS est de longueur `0`. Mémoïsez sur le couple de
positions `{i, j}`.

*Points d'appui pour vos tests :* `lcs("ABCBDAB", "BDCAB")` → **4** (par exemple
`"BCAB"`). `lcs("abc", "abc")` → **3**. `lcs("abc", "xyz")` → **0**. Une chaîne
vide → **0**. Propriété générale : la LCS n'est jamais plus longue que la plus
courte des deux chaînes.

```elixir
# Terrain libre. Choisissez A ou B, écrivez le module, PUIS écrivez
# vous-même les cellules de vérification par propriétés.
# Conseil : commencez par la version NAÏVE (sans cache), vérifiez qu'elle
# donne les bons petits cas, PUIS ajoutez le cache qui circule — et re-vérifiez
# que les valeurs n'ont pas bougé (seule la vitesse doit changer).

```

## Et maintenant ?

Vous avez parcouru tout le chemin : une récursion naïve qui explose, mesurée
au chronomètre, puis sauvée par un cache qui circule comme un accumulateur, et
enfin généralisée en une méthode, celle qui consiste à reconnaître des
sous-problèmes qui se recouvrent pour ne les résoudre qu'une seule fois.
Fibonacci, l'escalier, le rendu de monnaie et votre problème ouvert sont
quatre visages du même geste.

Ce que vous avez codé ici à la main — l'accumulateur, l'immutabilité qui force
à faire remonter l'état — reviendra à la séance 4, quand cet « accumulateur
qui voyage » deviendra un **état vivant dans un process**. La programmation
dynamique, à bien y regarder, n'est qu'un accumulateur particulièrement malin.
Bonne suite.