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

Question

这是我的问题：
不使用 MEMBER，完成递归函数 POS 的以下定义 这样，如果 L 是一个列表，E 是 L 的一个元素，那么 （POS E L） 返回第一个的位置 在 L 中出现 E，如果 E 不是 L 的元素，则 （POS E L） 返回 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

如果找不到元素，如何让它返回 0。由于它是函数式编程，我不能使用循环或变量。

Answer 1

你总是返回(+ 1 <recursive-call>) .但是，如果递归结果为零怎么办？您应该在计算结果之前检查该返回值。

• 如果发现匹配项，则返回 1
• 如果找不到结果，则递归计算，这将为您提供 R
• 如果 R 为零，则返回零
• 否则，返回 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)))