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