CODEWITHSUNDEEP
lispcommon-lispclisp
s24
s24

Reputation: 1

I have written a recursive function that checks a list to see if the element is present in lisp, but there's a stack overflow error

This is the member p method I tried. (Squash list is a method I made before that takes in the input of a list, and returns a list consisting of only atoms.)

(defun member-p (x y) 
    (squash-listr y)
    (if (listp y)
       (if (eq (cdr y) nil) nil)
       (t (eq (car y) x) x)
    )
    (member-p x (cdr y))
)

Test cases (I'll add more, but this is my first one) (print(member-p '2 '(2 4 5))) ;this test case should return 2 (the first argument of member-p)

Right now I'm getting a stack overflow error. I've checked my parentheses but am unable to find any issues.

Upvotes: 0

Views: 250

Answers (2)

Francis King
Francis King

Reputation: 1732

You need something like this:

(defun member-p (value lst)
   (if lst
      (if (eql value (car lst))
          value
          (member-p value (cdr lst)))
      'nil))

There are two base conditions:

  1. We find the value, return value
  2. We reach the end of the list before finding the value, return 'nil

Otherwise:

We run again on the cdr of the list.

By contrast, you don't have a base case. A value is calculated, which is thrown away, before the function is called again. Because '(listp y) is always true, only the first of the two values is calculated. Compiling the old version in Portacle shows the code that cannot be reached, underlined.

enter image description here

The execution of code can be seen using trace:

(trace member-p)
(member-p 2 '(1 2 3))

enter image description here

Upvotes: 0

Leo
Leo

Reputation: 1934

Note that member-p is called at the end in every case, even if y is nil. Thus the stack overflow. You should only call member-p in the case if y is not empty.
Further, the result of squash-listr is not used, thus you should ask yourself if it is really needed.

Upvotes: 1

Related Questions