Page 1 of 1

question about recursion (easy)

Posted: Tue Jul 15, 2008 8:08 am
by MaartenM
I tried my first LISP today. I got stuck trying to build a list of all intermediate values of the function 'c-series':

Code: Select all

(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

Code: Select all

(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,

Re: question about recursion (easy)

Posted: Tue Jul 15, 2008 8:59 am
by MaartenM
Ok, I managed to do it with the 'dotimes' macro:

Code: Select all

(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?

Re: question about recursion (easy)

Posted: Tue Jul 15, 2008 9:26 am
by AlexPaes
I think i'd do something like:

Code: Select all

(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.

Re: question about recursion (easy)

Posted: Tue Jul 15, 2008 9:27 am
by MaartenM
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?

Re: question about recursion (easy)

Posted: Tue Jul 15, 2008 10:10 am
by reuben.cornel
I wrote up two functions that do the same thing, except that for the first one you need to reverse the result.

Code: Select all

(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

Code: Select all

(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))))))))))

Re: question about recursion (easy)

Posted: Tue Jul 15, 2008 11:05 am
by dmgenp
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

Code: Select all

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.

Re: question about recursion (easy)

Posted: Tue Jul 15, 2008 11:17 am
by dmgenp
and here's my version of the function in question:

Code: Select all

;; 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:

Code: Select all

(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))))

Re: question about recursion (easy)

Posted: Tue Jul 15, 2008 2:34 pm
by MaartenM
Thanks guys, for the examples.
I now understand better how to implement left-hand side in Lisp with pure recursion instead of loops.

Re: question about recursion (easy)

Posted: Tue Jul 15, 2008 8:00 pm
by danb
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.

Code: Select all

(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)))