Recursion Question

[V_Suri]

I need to use recursion to print out each element of a list twice.
ex. rdouble'(1 2 3)
would return (1 1 2 2 3 3)
also rdouble'(1 (2 3) 4)
would return (1 1 (2 2 3 3) 4 4)

so far I have this function

Code: Select all

(defun rdouble (struct)
   (cond
     ((atom struct) struct)
     (t (cons (rdouble (car struct)) (cons (car struct) 
              (rdouble (cdr struct))
        )))))

this works fine for the first example but during the second example it prints
(11 (2 2 3 3) (2 3) 4 4)

How do I omit the second (2 3) while still doubling the values?
Can anyone help me fix this?

[nuntius]

[style note] The posted code could clarified by replacing the COND with an IF; but you may want to add a third clause, so leave the COND for now.

It can help to debug recursions by calling (trace rdouble) before running your code. You can turn this off by calling (untrace rdouble).

As to your question, the recursion is failing in the case when it is hitting a new sublist; the (car struct) is getting duplicated incorrectly. Then struct is not an atom, nor is (car struct). Maybe insert a case for this situation that generates one less CONS...

[Warren Wilkinson]

As nuntius says, your code is failing in the T condition of the cond clause when processing '(2 3). Your code says (cons (rdouble '(2 3)) (cons '(2 3) (rdouble -the-rest-))).

Code: Select all

(t (cons (rdouble (car struct)) (cons (car struct) 
              (rdouble (cdr struct))

Its interesting to see that in this clause you call rdouble on the first (car struct), but not on the second. Its sort of like you believe its an atom, but you're not willing to commit. If you were convinced that (car struct) was an atom, you could just write: (list* (car struct) (car struct) (rdouble (cdr struct))).

The case of (listp (car struct)) is different... because you DO recurse with rdouble ... but you actually don't want two results. Otherwise (list* (rdouble (car struct)) (rdouble (car struct)) (rdouble (cdr struct))) would work for both cases.

Code: Select all

(defun rdouble (i)
  (unless (null i)
    (if (listp (car i))
	(cons (rdouble (car i)) (rdouble (cdr i)))
	(list* (car i) (car i) (rdouble (cdr i))))))

(rdouble '(1 2 3))           ==> (1 1 2 2 3 3)
(rdouble '(1 (2 3) 4))       ==> (1 1 (2 2 3 3) 4 4)
(rdouble '(1 (2 3 (4 5)) 6)) ==> (1 1 (2 2 3 3 (4 4 5 5)) 6 6)

I wrote a accumulator-style version of this. I actually wrote it first, because being able to just dump two copies of the value onto an accumulation list just appealed to me.

Code: Select all

(defun rdouble (acc i)
  (when (null i) (return-from rdouble (nreverse acc)))
  (if (listp (car i))
      (rdouble (cons (rdouble nil (car i)) acc) (cdr i))
      (rdouble (list* (car i) (car i) acc) (cdr i))))

(rdouble nil '(1 2 3))           ==> (1 1 2 2 3 3)
(rdouble nil '(1 (2 3) 4))       ==> (1 1 (2 2 3 3) 4 4)
(rdouble nil '(1 (2 3 (4 5)) 6)) ==> (1 1 (2 2 3 3 (4 4 5 5)) 6 6)