CODEWITHSUNDEEP
common-lisp
trajce
trajce

Reputation: 21

Maximum of a list using recursion?

My task is to write function in lisp which finds maximum of a list given as argument of the function, by using recursion.I've tried but i have some errors.I'm new in Lisp and i am using cusp plugin for eclipse.This is my code:

(defun maximum (l)
  (if (eq((length l) 1)) (car l)  
   (if (> (car l) (max(cdr l)))
    (car l) 
     (max (cdr l))
))

Upvotes: 2

Views: 17144

Answers (8)

user4851482
user4851482

Reputation: 

(defun maxx (l)
   (if (null l)
       0
       (if(> (car l) (maxx(cdr l))) 
      (car l)
      (maxx (cdr l)))))

Upvotes: 0

Danil Gaponov
Danil Gaponov

Reputation: 1441

A proper tail-recursive solution 

(defun maximum (lst)
    (if (null lst)
        nil
        (maximum-aux (car lst) (cdr lst))))

(defun maximum-aux (m lst)
    (cond
        ((null lst) m)
        ((>= m (car lst)) (maximum-aux m (cdr lst)))
        (t (maximum-aux (car lst) (cdr lst)))))

Upvotes: 0

goku
goku

Reputation: 1

I made this, hope it helps and it is recursive.

(defun compara ( n lista)
   (if(endp lista)
       n
       (if(< n (first lista))
          nil
          (compara n (rest lista)))))

(defun max_lista(lista)
    (if (endp lista)
        nil
        (if(compara (first lista) (rest lista))
             (first lista)
             (max_lista(rest lista)))))

Upvotes: 0

Paty Rizk
Paty Rizk

Reputation: 17

if i need to do the max code in iteration not recursive how the code will be ?? i first did an array 

(do do-array (d l)
          setf b (make-array (length d))
          (do (((i=0)(temp d)) 
               ((> i (- l 1)) (return))
               (setf (aref b i) (car temp))
               (setq i (+ i  1))
               (setq temp (cdr temp))))

Upvotes: 0

Diego Sevilla
Diego Sevilla

Reputation: 29011

I see no answers truly recursive and I've written one just to practice Common-Lisp (currently learning). The previous answer that included a recursive version was inefficient, as it calls twice maximum recursively. You can write something like this:

(defun my-max (lst)
  (labels ((rec-max (lst actual-max)
             (if (null lst)
                 actual-max
                 (let ((new-max (if (> (car lst) actual-max) (car lst) actual-max)))
                   (rec-max (cdr lst) new-max)))))
    (when lst (rec-max (cdr lst) (car lst)))))

This is (tail) recursive and O(n).

Upvotes: 5

danlei
danlei

Reputation: 14291

If this isn't a homework question, you should prefer something like this:

(defun maximum (list)
  (loop for element in list maximizing element))

Or even:

(defun maximum (list)
  (reduce #'max list))

(Both behave differently for empty lists, though)

If you really need a recursive solution, you should try to make your function more efficient, and/or tail recursive. Take a look at Diego's and Vatine's answers for a much more idiomatic and efficient recursive implementation.

Now, about your code:

It's pretty wrong on the "Lisp side", even though you seem to have an idea as to how to solve the problem at hand. I doubt that you spent much time trying to learn lisp fundamentals. The parentheses are messed up -- There is a closing parenthesis missing, and in ((length l) 1), you should note that the first element in an evaluated list will be used as an operator. Also, you do not really recurse, because you're trying to call max (not maximize). Finally, don't use #'eq for numeric comparison. Also, your code will be much more readable (not only for others), if you format and indent it in the conventional way.

You really should consider spending some time with a basic Lisp tutorial, since your question clearly shows lack of understanding even the most basic things about Lisp, like the evaluation rules.

Upvotes: 17

Vatine
Vatine

Reputation: 21258

As written, that code implies some interesting inefficiencies (it doesn't have them, because you're calling cl:max instead of recursively calling your own function).

Function calls in Common Lisp are typically not memoized, so if you're calling your maximum on a long list, you'll end up with exponential run-time.

There are a few things you can do, to improve the performance.

The first thing is to carry the maximum with you, down the recursion, relying on having it returned to you.

The second is to never use the idiom (= (length list) 1). That is O(n) in list-length, but equivalent to (null (cdr list)) in the case of true lists and the latter is O(1).

The third is to use local variables. In Common Lisp, they're typically introduced by let. If you'd done something like:

(let ((tail-max (maximum (cdr l))))
   (if (> (car l) tail-max)
     (car l)
     tail-max))

You would've had instantly gone from exponential to, I believe, quadratic. If in combination had done the (null (cdr l)) thing, you would've dropped to O(n). If you also had carried the max-seen-so-far down the list, you would have dropped to O(n) time and O(1) space.

Upvotes: 2

tlehman
tlehman

Reputation: 5167

I think your problem lies in the fact that you refer to max instead of maximum, which is the actual function name.

This code behaves correctly:

(defun maximum (l)
  (if (= (length l) 1)
      (car l)
      (if (> (car l) (maximum (cdr l)))
          (car l)
          (maximum (cdr l)))))

Upvotes: 4

Related Questions