Just for fun (Project Euler #65) I want to implement the formula
n_k = a_k*n_k-1 + n_k-2
in an efficient way. a_k is either 1 or (* 2 (/ k 3)), depending on k.
I started with a recursive solution:
(defun numerator-of-convergence-for-e-rec (k)
"Returns the Nth numerator of convergence for Euler's number e."
(cond ((or (minusp k)) (zerop k) 0)
((= 1 k) 2)
((= 2 k) 3)
((zerop (mod k 3)) (+ (* 2 (/ k 3) (numerator-of-convergence-for-e-rec (1- k)))
(numerator-of-convergence-for-e-rec (- k 2))))
(t (+ (numerator-of-convergence-for-e-rec (1- k))
(numerator-of-convergence-for-e-rec (- k 2))))))
which works for small k but gets pretty slow for k = 100, obviously.
I have no real idea how to transform this function to a version with could be tail-call optimized. I have seen a pattern using two accumulating variables for fibonacci numbers but fail to transform this pattern to my function.
Is there a general guideline how to transform complex recursions to tco versions or should I implement an iterative solution directly.?