1

I am a new lisp programmer and I am trying to create my first recursive lisp function to return the larger of two lists. Every time I run the function it seems to crash as I guess my base case isn't being met. Here's the code I have. 

(defun longest (l1 l2)
  (cond ((null l1) (l2))
        ((null l2) (l1))
        (t (rest l1) 
           (rest l2) 
           (longest l1 l2))
  )
)

I know this wouldn't work for the case when both lists are the same length, but I just wanted to get something working first. I understand this could also be achieved with a while loop but for the purpose of learning I wanted to use recursion.

Why does this code never terminate?

Improve this question

3 Answers 3

Reset to default
4

This code never terminates, because you calling longest with the same input data again and again. rest returns all elements of the list except the first one, not modifies the list, originally passed as argument. And also you have other errors:

(defun longest (l1 l2)
  (cond ((null l1) (l2)) ;; <= will give error,
        ((null l2) (l1)) ;;  because there is no such function like l2
        (t (rest l1) ;; <=  result ignored
           (rest l2) ;; <=  result ignored
           (longest l1 l2)))) ;; <= called with the same l1 and l2

Obviously, it'll run until you run out of stack. The right code for expected behavior will be:

(defun longest (l1 l2)
  (cond ((null l1) l2)
        ((null l2) l1)
        (t 
         (longest (rest  l1) (rest  l2)))))

And note,that you probably can't get what you expected by this approach, because longest every time will take CDR of lists, so it'll return just rest elements of longest list, so if you call (longest '(1 2 3) '(1 2)) you'll get just '(3), what may not what your expecting.

If you want it really return all longest list, you must modify your code.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

This makes so much sense, stupid mistake on my part, but it's to be expected as I'm new to this language. Thank you very much my friend.
@Jake, Note, that you probably can't do what you want. See edited answer.
Ah yes, good point, I will have to store both lists in some sort of global variables the first time I run the function?
@Jake, I'm just wondering, can't your just substract length one of the lists from other?
Yes but that wouldn't make use of recursion, I am doing problems that will help me to understand recursion in lisp, admittedly using recursion for this problem just complicates it further :).
2

A useful trick for recursion is to build a local "worker" function that finds the key information. The result of the worker than then be appropriately "processed" to give the final answer that you need. This is similar to the way that iteration is often used in imperative languages, but much more flexible.

For example, in your example, a good way to solve this is:

(defun longest (l1 l2)
  (labels ((first-longer (a b)
      (cond ((null a) nil)
            ((null b) t)
            (t (first-longer (rest a) (rest b))))))
    (if (first-longer l1 l2) l1 l2)))

Examples of use:

(longest '(5 6 7 8) '(1 2 3)) --> (5 6 7 8)
(longest '(5 6 7) '(1 2 3 4)) --> (1 2 3 4)
(longest '(5 6 7) '(1 2 3)) --> (1 2 3)

Notice that there is an ambiguity in how equal-length lists should be handled: the last example might as well have returned (5 6 7)

Improve this answer

Comments

1

In your code you call yourself without altering any of the arguments when none of the base cases hit. The result would be that the default case will always hit on all the following iterations. It seems you think rest somehow mutates it's argument, which it doesn't. It returns a result without changing the original argument. (rest '(1 2 3)) ; ==> (2 3) but (1 2 3) is still (1 2 3) and not (2 3). If you change with (rest x) where x is (1 2 3) the result would still be (2 3) and x will still be (1 2 3).

Here is my take on it:

;; return the longest of two lists
(defun longest (l1 l2)
  (labels ((aux (tl1 tl2)
             (cond ((null tl2) l1)
                   ((null tl1) l2)                   
                   (t (aux (rest tl1) (rest tl2))))))
    (aux l1 l2)))

You'll always get the first argument if they are of equal size. It's the same as with a stable sort where all elements have the same weight you'll always get the same first value you already had. An alternative to this would be to do return nil when they are of equal length since none are longest.

Simplicity is usually much better. Here is how I would have implemented it:

(defun longest (l1 l2)
  (if (< (length l1) 
         (length l2))
      l2
      l1))
Improve this answer

5 Comments

+1 on the first code though I disagree on the second. length is not O(1).
@WillNess Neither of them are O(1), but it's true that the first is an optimization of the second. CL fares fairly well with the second example with moderately large lists so unless you know you are dealing with very large lists or possible circular ones the second is shorter to write and much easier to read :) (In ikarus Scheme I've seen the same optimization do no improvement due to wicket faster length)
examining a cdr is always O(1).
@WillNess That's true but you do aux (min l1 l2) times while using length on both lists does cdr (+ l1 l2) times. Slight optimization, but doesn't have a better big O.
O(min(m,n)) is very much different from O(m+n) which is O(max(m,n)).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.