Clojure - La Recurrència amb Trampolí W83336

Es pot demostrar que la recurrència $u_{n+2}=5 \times u_{n+1} - 6 \times u_{n}$, amb $u_0 = 0$ i $u_1 = 1$ és tal que per a tot $n$, $u_n = 3^n - 2^n$.

L’estudiant que no ho sap, però vol conèixer el valor d’$u_n$ per a qualsevol $n$, podria ser tan ingenu d’implementar la següent funció d’una manera molt ineficient, fent servir la definició matemàtica:

(defn recurrencia [n]
   (cond
      (or (= n 0)  (= n 1))   n
      :else (let [rm1   (recurrencia (dec n))
                  rm2   (recurrencia (dec (dec n)))]
              (-' (*' 5 rm1) (*' 6 rm2)))))

Passeu aquesta funció a continuation passing style per obtenir-ne la versió recursiva final. Anomeneu-la recurrencia-cps.

Després, trampolinitzeu recurrencia-cps per evitar d’obtenir l’error de Stack Overflow. Anomeneu-la recurrencia-t.

Observacions

Cal que envieu un fitxer amb la definició de les dues funcions recurrencia-cps i recurrencia-t.