Sigui la funció que retorna la seqüència dels moviments que cal fer per resoldre el problema de les Torres de Hanoi per a anelles o discos:
(defn move [n from to aux]
(if (= n 1)
[{:from from :to to}]
(concat
(move (dec n) from aux to)
[{:from from :to to}]
(move (dec n) aux to from))))
Si definim:
(defn torres-de-hanoi [n]
(move n "A" "C" "B"))
i executem obtenim la seqüència (pretty printed):
({:from "A", :to "C"}
{:from "A", :to "B"}
{:from "C", :to "B"}
{:from "A", :to "C"}
{:from "B", :to "A"}
{:from "B", :to "C"}
{:from "A", :to "C"})
Es demana que transformeu aquesta funció a recursiva final fent servir CPS, anomenem-la move-cps, i després feu servir move-cps com a funció auxiliar per poder fer servir i definir la funció "trampolinitzada" (l’execució de la qual consumeix una quantitat constant de pila d’execució).
Input
(towers-of-hanoi-t 3)
Output
({:from A, :to C} {:from A, :to B} {:from C, :to B} {:from A, :to C} {:from B, :to A} {:from B, :to C} {:from A, :to C})