Как написать рекурсию в lisp?

Question

Мне нужна ваша огромная помощь. Я хочу написать функцию на Лиспе с именем rec, функция получает список следующим образом: (rec '(10 (12 (5 2 2) 9) (2 14 (4 (3 1 1) 5)))) мой код должен проверить, равна ли сумма внутреннего списка номеру внешнего списка (5 + 2 + 2 = 9, это равно 9, тогда я иду дальше 9 + 9 + 12 = 30, 3 + 3 + 1 = 5 это равно 5, тогда 5 + 5 + 4 = 14 это равно 14, 14 + 14 + 2 = 30 и 30 равно 30, по крайней мере, я добавляю 10 к 30 + 30 и мою сумму всего списка 70. Если моя сумма равна числам, я верну сумму всего списка, иначе я верну ноль. Я надеюсь, вы понимаете, что я имею в виду ... теперь я хочу решить это с помощью рекурсии, я пробовал кое-что, но Я не могу решить это, я надеюсь, что кто-то может помочь мне в дальнейшем ...

(defun rec(list)

)

(rec '(10 (12 (5 2 2) 9) (2 14 (4 (3 1 1) 5))))

Answer 1

Как реализовать эту функцию будет легче, если вы уточнить , что нужно сделать .

Ввод

Ваш ввод - список, но не какой-либо список.Давайте назовем этот конкретный вид списка узлом .

A узел - это либо пустой список, либо список из 3 элементов (v n1 n2), где:

• v - это число,
• n1 (соответственно n2 )это либо узел , либо число .

Выход

При вызове rec на узле , он должен вывести либо число , либо nil .

Outline

Давайте определим вспомогательную функцию num, которая принимает либо числоили узел и возвращает число или ноль, вызывая rec:

• (num n) для номера n должен вернуть n
• (num n) дляузел n должен вернуть (rec n)

Тогда rec можно определить следующим образом:

• (rec nil) должно быть nil
• (rec (v n1 n2)) должен вернуть (+ v (num n1) (num n2)), когда (num n1) и (num n2) равны числам.В любом другом случае rec должен возвращать nil.

Пример

Ниже приведен один из возможных способов его реализации, и он опирается на операторы, такие как определения локальных функций (FLET), переключение на основе типа значения (TYPECASE) и метод раннего возврата .Смотрите также DESTRUCTURING-BIND.Использование логических операторов (и / или) полезно для объединения возможных промежуточных результатов NIL:

(defun rec (node)
  (flet ((num-or-fail (n)
           (or (typecase n
                 (number n)
                 (cons (rec n)))
               (return-from rec))))
    (and node
         (destructuring-bind (v n1 n2) node
           (let ((v1 (num-or-fail n1))
                 (v2 (num-or-fail n2)))
             (and (= v1 v2)
                  (+ v v1 v2)))))))

В REPL (командной строке) вы можете активировать трассировку для rec:

CL-USER> (trace rec)

И затем вы можете проверить:

CL-USER> (rec '(10 (12 (5 2 2) 9) (2 14 (4 (3 1 1) 5))))

Выше возвращается 70 и выводится следующая трассировка в SBCL:

0: (REC (10 (12 (5 2 2) 9) (2 14 (4 (3 1 1) 5))))
  1: (REC (12 (5 2 2) 9))
    2: (REC (5 2 2))
    2: REC returned 9
  1: REC returned 30
  1: (REC (2 14 (4 (3 1 1) 5)))
    2: (REC (4 (3 1 1) 5))
      3: (REC (3 1 1))
      3: REC returned 5
    2: REC returned 14
  1: REC returned 30
0: REC returned 70

Ранний возврат может даже сбежать из самого внешнего вызовапоскольку это означает, что весь результат равен NIL (немного похоже на исключение).Вы также можете сделать rec локальной функцией, взаимно рекурсивной с num-or-fail, и по-разному назвать вашу основную функцию:

(defun sumtree (node)
  (labels ((num-or-fail (n)
             (or (typecase n
                   (number n)
                   (cons (rec n)))
                 (return-from sumtree)))
           (rec (node)
             (and node
                  (destructuring-bind (v n1 n2) node
                    (let ((v1 (num-or-fail n1))
                          (v2 (num-or-fail n2)))
                      (and (= v1 v2)
                           (+ v v1 v2)))))))
    (rec node)))

Здесь выше, когда один из промежуточных результатов равен nil, return-from раскручивает весь стек рекурсивных вызовов и напрямую возвращает nil.

Answer 2

Мне кажется, что это будет работать только в том случае, если во всех списках есть 3 элемента. Давайте назовем это втрое.

(defun triplep (e)
  (and (listp e)
       (= 3 (length e)))

;; test
(triplep 5)        ; ==> nil
(triplep '(3 4 5)) ; ==> t

Мне не нравится имя rec, поэтому я назову его sum-triple. Я догадываюсь:

(sum-triple 5) ; ==> 5
(sum-triple '(3 1 1)) ; ==> 
(let ((x2 (sum-triple 1))
      (x3 (sum-triple 1))
  (if (= x2 x3)
      (+ (sum-triple 3) x2 x3)
      0))

Теперь, чтобы вернуть его '(), вам нужно обернуть его. Первый вызов должен отличаться от всех остальных, чтобы вы могли выпрыгнуть из помощника и сделать что-то совершенно другое при необходимости:

(defun my-fun (x)
  (labels ((helper (x acc) ; acc here is just to show you can hold state
             ;; actual implementation that calls itself
             ;; if it finds a bad value it can short cut with
             (return-from my-fun '()))
    (helper x '())))