question about recursion (easy)

I tried my first LISP today. I got stuck trying to build a list of all intermediate values of the function 'c-series':

(defun even (n) (= (mod n 2) 0))
(defun square (x) (* x x))

(defun c-series (n a)
  (if (= n 0)
      a
      (if (even n)
	  (log (c-series (- n 1) a))
	  (square (c-series (- n 1) a))
	  )
      )
  )

What if I wanted to print out a finite list of all the intermediate c-series values?
A list containing

(let (a 5)
((c-series (1 a)) (c-series (2 a)) (c-series (3 a)) ...
)

Of course, with actual reuse of the previous results.
I just can't seem to find a way to fit the recursion in there. (I've played with Haskell before and just can't get my head around how to implement this type of recursion in Lisp). Do I really need a helper function? Thanks for helping me on my way,

Ok, I managed to do it with the 'dotimes' macro:

(defun cseries-list (n a)
  (let ((l (list a)))
    (dotimes (i n)
       (if (even i)
	  (push (log (car l)) l)
	  (push (square (car l)) l)))
    (nreverse l)))

Is this the 'Lisp' way?

I think i'd do something like:

(defun cseries-list (n a)
   (loop for i from 1 upto n collect (c-series i a)))

Not sure if that's more lispy than what you provided, but has the advantage of using the c-series function thus better code re-use. One sidenote is that you don't need to define the even function since there's already a evenp function that you can use test if some argument is even.

But this recalculates a large number of recursive branches redundantly, doesn't it? Or is there some magic goign on there I'm not aware of?

I wrote up two functions that do the same thing, except that for the first one you need to reverse the result.

(defun reverse-recursive-c-series(n a)
  (if (zerop n) 
      (list a)
      (let ((return-a (reverse-recursive-c-series (- n 1) a)))
	(cond ((evenp (- n 1)) (cons  (log (first return-a)) return-a))
	      ((oddp  (- n 1)) (cons  (square (first return-a)) return-a))))))

Same function where you don't need to reverse the result

(defun recursive-c-series(n a)
  (if (zerop n) 
      (list a )
      (let ((return-a (recursive-c-series (- n 1) a)))
	(cond ((evenp (- n 1)) (append  return-a (list (log (first (last return-a))))))
	      ((oddp  (- n 1)) (append return-a (list (square (first (last return-a))))))))))

Haskell gives lazy lists and memoization for them out-of-the-box.

for common lisp, you can use this library:

http://cl-heresy.sourceforge.net/Heresy.htm

The clichéd Fibonacci example:

(Request 1000000th element in Fibonacci sequence using self-referencing list)

(nth/ 1000000
 (self-ref-list/ fib (list*/ 1 1 (map/ #'+ fib (tail/ fib)))))

; self-ref-list internally memoized (to allow order-n solution); but with deferred creation (until extract time) to prevent storage bloat by holders of list reference.

and here's my version of the function in question:

;; generate a list of first n C-series values
(defun c-series-list (n a) 
  (when (zerop n) (return-from c-series-list)) 
  (labels 
    ((c-s (n a) 
      (if (= 1 n) 
          (list a) 
          (let* ((rest (c-s (- n 1) a)) 
                 (prev (car rest))) 
                (cons (if (evenp n) 
                          (log prev) 
                          (* prev prev)) 
                      rest))))) 
    (nreverse (c-s n a))))

and the loop-based version:

(defun c-series-list (n a) 
  (loop for i from 2 to n 
        with result = (list a) 
        for prev = (first result) 
        do (push (if (evenp i) 
                   (log prev) 
                   (* prev prev)) 
                 result) 
        finally (return (nreverse result))))

Thanks guys, for the examples.
I now understand better how to implement left-hand side in Lisp with pure recursion instead of loops.

MaartenM wrote:I now understand better how to implement left-hand side in Lisp with pure recursion instead of loops.

Here's another way. It avoids both appending and reversing.

(defun c-series (n a)
  (labels
      ((c-cons (i x)
         (unless (> i n)
           (cons x (c-cons (+ i 1)
                           (if (oddp i) (log x) (* x x)))))))
    (c-cons 0 a)))