First, note that memoization is probably the easiest way to optimize your code: it does not cancel the workflow; you call your function with given k, and it returns to zero to calculate the previous values, but with a cache. However, if you want to convert your function from recursive to iterative with TCO, you will have to calculate things from zero to k and pretend that you have a constant-sized stack / memory.
Step function
First write a function that calculates the current n given k, n-1 and n-2:
(defun n (k n1 n2) (if (plusp k) (case k (1 2) (2 3) (t (multiple-value-bind (quotient remainder) (floor k 3) (if (zerop remainder) (+ (* 2 quotient n1) n2) (+ n1 n2))))) 0))
This step should be simple; here I rewrote your function a bit, but in fact I only extracted the part that computes n, given the previous n and k.
Modified function with recursive (iterative) calls
Now you need to call n from k from 0 to the maximum value that you want to calculate, with the name m in the future. So I'm going to add the parameter m , which controls when the recursive call stops, and call n recursively with the arguments changed. You can see that the arguments are shifted, the current n1 is the next n2 , etc.
(defun f (mk n1 n2) (if (< mk) n1 (if (plusp k) (case k (1 (fm (1+ k) 2 n1)) (2 (fm (1+ k) 3 n1)) (t (multiple-value-bind (quotient remainder) (floor k 3) (if (zerop remainder) (fm (1+ k) (+ (* 2 quotient n1) n2) n1) (fm (1+ k) (+ n1 n2) n1))))) (fm (1+ k) 0 n1))))
That's all, except that you do not want to show this interface to your user. The actual function g correctly loads the initial call to f :
(defun g (m) (fm 0 0 0))
The trace for this function is in the form of an arrow ">", which is the case with tail recursive functions (tracing probably prevents tail call optimization):
0: (G 5) 1: (F 5 0 0 0) 2: (F 5 1 0 0) 3: (F 5 2 2 0) 4: (F 5 3 3 2) 5: (F 5 4 8 3) 6: (F 5 5 11 8) 7: (F 5 6 19 11) 7: F returned 19 6: F returned 19 5: F returned 19 4: F returned 19 3: F returned 19 2: F returned 19 1: F returned 19 0: G returned 19 19
Driver function with loop
The part that can be a bit complicated or make it difficult to read the code is when we introduce tail recursive calls inside the original function n . I think it is better to use a loop because:
- unlike a tail recursive call, you can guarantee that the code will behave the way you want without worrying if your implementation will actually optimize tail calls or not.
- the code for the function of step
n simpler and expresses only what is happening, instead of describing in detail how (tail recursive calls are just implementation details here).
Using the specified function n you can change g to:
(defun g (m) (loop for k from 0 to m for n2 = 0 then n1 for n1 = 0 then n for n = (nk n1 n2) finally (return n)))
Is there a general rule on how to convert complex recursions to tco, or should I implement an iterative solution directly?
Find the step function that takes the calculations from the base case to the general case and puts the intermediate variables as parameters, in particular, the results of past calls. This function can call itself (in this case it will be tail recursive, because you need to calculate all the arguments first) or just call in a loop. You must be careful when calculating the initial values, you may have more angular cases than with a simple recursive function.
see also
Scheme named let , macro recur in Common Lisp and recur special form in Clojure.