Clojure - La Recurrència amb Trampolí W83336

Es pot demostrar que la recurrència u_n+2=5 × u_n+1 − 6 × u_n, amb u₀ = 0 i u₁ = 1 és tal que per a tot n, u_n = 3ⁿ − 2ⁿ.

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.