我搜索元素的递归函数总是返回nil

Question

我想实现一个在列表中搜索元素的递归函数。

我做了以下代码：

(defun encontrar (element lista)
  (if (atom lista)
    (if (eq lista element)
      t
      nil
    )
    (progn
      (loop for element_lista in lista
        do(if (eq (encontrar element element_lista) t)
          t
        )
      )
      nil
    )
  )
)

我总是得到零作为回报。我尝试了下面的示例，该示例应返回t：

(encontrar #\x '(#\P #\y (#\f \x) #\A))

Answer 1

让我们尝试找出错误。

由于它是一个递归函数，因此trace-ing可以轻松地向我们显示所有中间步骤：

(trace encontrar)

现在，运行相同的测试：

(encontrar #\x '(#\P #\y (#\f \x) #\A))

0: (ENCONTRAR #\x (#\P #\y (#\f |x|) #\A))
    1: (ENCONTRAR #\x #\P)
    1: ENCONTRAR returned NIL
    1: (ENCONTRAR #\x #\y)
    1: ENCONTRAR returned NIL
    1: (ENCONTRAR #\x (#\f |x|))
      2: (ENCONTRAR #\x #\f)
      2: ENCONTRAR returned NIL
      2: (ENCONTRAR #\x |x|)
      2: ENCONTRAR returned NIL
    1: ENCONTRAR returned NIL
    1: (ENCONTRAR #\x #\A)
    1: ENCONTRAR returned NIL
0: ENCONTRAR returned NIL

如果您查看痕迹，应该会感到惊讶|x|。这是一种用于按字面写符号的表示法，无需大小写转换（取决于当前的可读表；通常在读取符号时将它们大写），并带有应加引号的字符（如空格）。这|x|是名称为字符串的符号"x"（注意为小写）。它不是一个字符，由于输入错误而可能出现在列表中，您可能要写#\x但要写\x，这是引用符号的另一种方式。

让我们修复测试：

(encontrar #\x '(#\P #\y (#\f #\x) #\A))


0: (ENCONTRAR #\x (#\P #\y (#\f #\x) #\A))
  1: (ENCONTRAR #\x #\P)
  1: ENCONTRAR returned NIL
  1: (ENCONTRAR #\x #\y)
  1: ENCONTRAR returned NIL
  1: (ENCONTRAR #\x (#\f #\x))
    2: (ENCONTRAR #\x #\f)
    2: ENCONTRAR returned NIL
    2: (ENCONTRAR #\x #\x)
    2: ENCONTRAR returned T
  1: ENCONTRAR returned NIL
  1: (ENCONTRAR #\x #\A)
  1: ENCONTRAR returned NIL
0: ENCONTRAR returned NIL

结果仍然是NIL，但请注意中间层(ENCONTRAR #\x #\x)返回T。不知何故，该结果不会传播回去。

您进行递归调用的其他情况如下：

(progn
  (loop for element_lista in lista
   do(if (eq (encontrar element element_lista) t)
      t
    )
  )
  nil
) 

首先，格式化不是惯用的，让我们重写一下：

(progn
  (loop
     for element_lista in lista
     do (if (eq (encontrar element element_lista) t)
            t))
  nil)

这里有很多东西：

• 表达式(progn e1 .. en)具有值之一en（这就是nin的progn含义）。所以在这里，您有(progn (loop ...) nil)，因此第一个表达式的值将被丢弃，返回值是nil（并且循环不执行跳转）

• (if test t)与相同(if test t nil)，等同于仅写入test（返回的值可能不是字面值t，但不是nil，因此在布尔上下文中将其解释为true。

• 同样，测试(if (eq test t) t)是多余的，因为EQ已经返回T或NIL（感谢@Kaz指出错误）。

• 在(eq lista element)（基本情况下）中，eq不应将其用于比较可移植程序中的字符，因为实现可能会为的值返回NIL char=。如果要允许字符以外的其他类型的值，请使用eql，或者equalp如果您不介意测试以递归方式遍历这些值，请使用；但是无论如何都不要使用，eq因为它会检查两个对象是否相同，但是具有相同表示形式的字符（和数字）可能是不同的对象（例如bignums）。

• loop在所有情况下，您的返回值为nil。您计算的内容将do被丢弃，因为do它有副作用。如果要循环直到测试为真，则使用(loop for x in list thereis (test x))或等效地(some #'test list)。

这应该可以帮助您调试代码。