question about recursion (easy)

Discussion of Common Lisp
Post Reply
MaartenM
Posts: 5
Joined: Tue Jul 15, 2008 7:55 am

question about recursion (easy)

Post by MaartenM » Tue Jul 15, 2008 8:08 am

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,

MaartenM
Posts: 5
Joined: Tue Jul 15, 2008 7:55 am

Re: question about recursion (easy)

Post by MaartenM » Tue Jul 15, 2008 8:59 am

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?

AlexPaes
Posts: 21
Joined: Sat Jun 28, 2008 3:38 am
Location: Lisbon, Portugal

Re: question about recursion (easy)

Post by AlexPaes » Tue Jul 15, 2008 9:26 am

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.
CL-USER> (setf *boss* (make-instance 'smart-person))
NIL
CL-USER>

MaartenM
Posts: 5
Joined: Tue Jul 15, 2008 7:55 am

Re: question about recursion (easy)

Post by MaartenM » Tue Jul 15, 2008 9:27 am

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?

reuben.cornel
Posts: 7
Joined: Sun Jun 29, 2008 9:48 am
Location: Sterling, Virginia, USA
Contact:

Re: question about recursion (easy)

Post by reuben.cornel » Tue Jul 15, 2008 10:10 am

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

dmgenp
Posts: 13
Joined: Sat Jun 28, 2008 10:15 am

Re: question about recursion (easy)

Post by dmgenp » Tue Jul 15, 2008 11:05 am

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.

dmgenp
Posts: 13
Joined: Sat Jun 28, 2008 10:15 am

Re: question about recursion (easy)

Post by dmgenp » Tue Jul 15, 2008 11:17 am

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

MaartenM
Posts: 5
Joined: Tue Jul 15, 2008 7:55 am

Re: question about recursion (easy)

Post by MaartenM » Tue Jul 15, 2008 2:34 pm

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

danb
Posts: 35
Joined: Sat Jun 28, 2008 1:05 pm
Location: Urbana, Illinois, US
Contact:

Re: question about recursion (easy)

Post by danb » Tue Jul 15, 2008 8:00 pm

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

Post Reply