使用 LISP 递归查找列表中的元素位置

Question

这是我的问题：
在不使用 MEMBER 的情况下，完成以下递归函数 POS 的定义这样如果 L 是列表并且 E 是 L 的元素，则 (POS E L) returns 第一个的位置 E 在 L 中出现，如果 E 不是 L 的元素，则 (POS E L) returns 0.

这是提出的解决方案：

(DEFUN POS (E L)
(COND ((ENDP L)  0)
((EQUAL E (CAR L)) 1 )
(T 
      (+ 1 (POS E (CDR L)) )   

  )))

如果我要查找的元素在列表中，则该算法工作正常。我的问题是，当元素不在列表中时，我将获得列表的长度。

示例：

list[1,2,3,4] Find: 5  will reurn 4

如果找不到元素，我如何将其设置为 return 0。因为它是函数式编程，所以我不能使用循环或变量。

Answer 1

你总是return(+ 1 <recursive-call>)。但是如果递归结果为零呢？您应该在计算结果之前检查 return 值。

如果您找到一个事件，return 1
如果没有找到结果，递归计算，得到 R
如果 R 为零，return 为零
否则，return R + 1

顺便说一句，Common Lisp 的方式是：

(or (position E L :test #'equal) 0)

Answer 2

正如@coredump 所解释的那样，问题是您总是将结果加 1，即使您没有找到该元素。我会通过向函数 POS:

添加一个额外参数来跟踪列表中的当前位置

(defun pos (element list &optional (start 0))
  (cond ((endp list) 0)
        ((equal element (first list)) (1+ start))
        (t (pos element (rest list) (1+ start)))))

测试：

(pos 'a '(b a c d a))
2

(pos 'a '(a d a f g))
1

(pos 'w '(a b c d e f))
0

一个额外的好处：由于递归调用处于尾调用位置，此函数生成迭代过程（但是，ANSI Common Lisp 不保证它会进行尾调用优化! AFAIK，CLisp 不会这样做；SBCL 和 CCL 会为优化代码做这件事，请参阅 DECLARE）。更惯用的 Common Lisp 解决方案将使用 LOOP:

(defun pos (element list)
  (loop for x in list
     counting x into pos
     when (equal element x)
     return pos
     end
     finally (return 0)))

使用 LISP 递归查找列表中的元素位置

Recursively find element position in list using LISP

lisp

recursion

functional-programming