Моя рекурсивная функция для поиска элемента всегда возвращает ноль - PullRequest
Новая
       6

Моя рекурсивная функция для поиска элемента всегда возвращает ноль

1 голос
/ 07 ноября 2019

Я хочу реализовать рекурсивную функцию, которая ищет элемент в списке.

Я сделал следующий код: 

(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))

1 Ответ

7 голосов
/ 07 ноября 2019

Давайте попробуем найти ошибку.

Поскольку это рекурсивная функция, trace -ing может легко показать нам все промежуточные шаги: 

(trace encontrar)

Теперь запустите то же самоеtest: 

(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 (это то, что означает n в progn). Итак, у вас есть (progn (loop ...) nil), поэтому значение первого выражения отбрасывается, а возвращаемое значение равно nil (и цикл не выполняет переходов)

  • (if test t) - этотак же, как (if test t nil), что эквивалентно простой записи test (возвращаемое значение может быть не буквально t, но оно не равно нулю, поэтому в логическом контексте оно будет интерпретировано как true.

  • аналогично, тестирование (if (eq test t) t) является избыточным, поскольку EQ уже возвращает либо T, либо NIL (спасибо @Kaz за указание на ошибки).

  • в (eq lista element) (базовый случай), eq следует не использовать для сравнения символов в переносимых программах, поскольку реализация может возвращать NIL для значений, которые char=. Если вы хотите разрешить значения другого типа, кромесимволов, используйте eql или, возможно, equalp, если вы не возражаете против теста для рекурсивного обхода значений, но в любом случае не используйте eq, потому что он проверяет, являются ли два объекта идентичными , но символы (и цифры), имеющие одинаковое значениеepresentation может быть различными объектами (например, bignums).

  • возвращаемое значение вашего loop равно нулю во всех случаях. То, что вы вычисляете в do, отбрасывается, потому что do используется для побочных эффектов;если вы хотите выполнить цикл до тех пор, пока тест не станет истинным, используйте (loop for x in list thereis (test x)) или, что то же самое, (some #'test list).

Это должно помочь вам в отладке кода.

...