Recursive euclidean distance

问题:

I was tasked to write a recursive euclidean distance. I have been googling around but could not find any sample. I understand the function of euclidean distance and has no problem writing it in an iterative manner as shown below. Is there anyone who could advise me on how I should start for the recursive function? The requirement is the same as the iterative version. Thanks.

 (defun euclidean-distance-it (p q)  
  (cond
   ((or (null p) (null q)) nil) ;return nil if either list is null
   ((or (atom p) (atom q)) nil) ;return nil if either list is an atom
   ((or (null (cdr p)) (null (cdr q))) nil);return nil if either list contains less than two inputs

   ((or (not (null (car(cdr(cdr p))))) (not (null (car(cdr(cdr q)))))) nil) ;return nil if either list contains more than two inputs
   ((or (or (not (numberp (car p))) (not (numberp (cadr p)))) (or (not (numberp (car q))) (not (numberp (cadr q))))) nil);return nil if any of the four entires aren't numbers
   (T (sqrt (+ (expt (- (car p) (car q)) 2)
              (expt (- (cadr p) (cadr q)) 2)))))) ;Calculate the euclidean distance

回答1:

The only time recursive algorithm for this would be sensible if the input are two vectors (represented by lists) of any dimension, not only 2 or 3. In this case this will compute the square of the distance:

(defun sq-euclid-distance (p q)
  (cond ((or (null p) (null q)) 0)
        (t (+ (expt (- (car p) (car q)) 2)
              (sq-euclid-distance (cdr p) (cdr q))))))

To get SQRT out of it you would need to make it into a auxiliary helper and make a driver computing the square root.

(defun euclid-distance (p q) (sqrt sq-euclid-distance p q))

PS. I am not checking if p and q are atoms, but they can be treated as 1-dimensional vectors. Returning NIL from the function that is expected to provide a numerical value is not a great idea.

回答2:

Looking at this Haskell thread, I think your task is more likely to compute the distance of n-dimensional vectors, i.e. sqrt((x1-y1)^2 + ... + (xn-yn)^2).

In your example there is no iteration, you just access elements inside two lists. In other words: you assume that P and Q contains 2 elements and I think the question is to generalize this to N elements.

Moreover, you are doing many useless checks in order to return nil instead of letting errors be signaled. For example, if the lists do not contain numbers, you should probably not return nil.

I would rewrite your version like this:

(defun euclidean-distance-it (p q)
  (destructuring-bind (x1 x2) p
    (destructuring-bind (y1 y2) q
      (sqrt (+ (expt (- x1 y1) 2)
               (expt (- x2 y2) 2))))))

With a recursive version, I consider that p and q are two mathematical vectors, so that p contains different coordinates (p1, ..., pn), which differs from your implementation where p contains all x's and q all y's.

So, you have to compute (pi - qi)^2 for each for pair (pi, qi) of elements taken in parallel from p and q, sum the intermediate values and take the square root. With high-order functions, you don't even need to use recursion.

I won't spoil you the recursive answer, but here is a higher-order function version:

(defun distance (p q) 
  (sqrt
    (reduce #'+ 
      (map 'list
        (lambda (px qx) (expt (- px qx) 2)) 
        p q))))

And another one with loop:

(defun distance (p q)
  (sqrt (loop for px in p
              for qx in q
              sum (expt (- px qx) 2))))