Попытка рекурсивно напечатать треугольник в lisp

Question

Попытка рекурсивно напечатать треугольник в lisp. Я получаю переполнение, но я не знаю откуда. Имейте в виду, я новичок в программировании на Лиспе.

(defun triangle (n)
    (if (not (oddp n))(progn 
        (print "This is not an odd integer")
        (return-from triangle n)))   
    (if (< n 1) '())
            (setf lst (cons (car(list n)) (triangle (- n 2))))
    (print lst))

(треугольник 7)

Answer 1

Давайте рассмотрим некоторые части вашего кода.

(if (not (oddp n)) (progn (print ...) (return-from ...)))

Если у вас есть if только с одной веткой, подумайте об использовании when или unless, особенно если вы ставите progn в подчиненной форме. Например, вы можете избавиться от progn, переключившись на when:

(when (not (oddp n))
  (print ...)
  (return-from ...))

Выражение (when (not ...)) совпадает с (unless ...):

(unless (oddp n)
  ...)

Здесь вы печатаете сообщение об ошибке и возвращаетесь из функции. Common Lisp имеет исключения, которые сделаны для тех случаев использования. Обычно вы вызываете (error "Not an odd integer: ~d" n), но здесь вы можете положиться на поведение по умолчанию assert и заменить всю проверку на:

(assert (oddp n))

Если вы попробуете это с 2, вы получите ошибкус сообщением, похожим на это:

The assertion (ODDP N) failed with N = 2.

Что достаточно для тестов.

Тогда у вас есть следующее выражение:

(cons (car (list n)) (triangle (- n 2)))

Когда вы пишете (list e1 e2 .. en), это как если бы вы написали:

(cons e1 (cons e2 (... (cons en nil))))

В вашем случае это означает, что (list n) - это то же самое, что и

(cons n nil)

Но так как вы затем делаете следующее:

(car (cons n nil))

Вы просто выделяете ячейку и отбрасываете ее только для доступа к n. Все выражение можно заменить на n.

В-третьих, вы также используете setf для lst, где lst - неопределенная переменная. В большинстве реализаций (но на самом деле это поведение не определено), что бы установить глобальную привязку для lst, и это плохая практика - устанавливать глобальные переменные внутри функций. Вместо этого вы можете использовать let:

(let ((lst (cons n (triangle (- n 2)))))
  (print lst))

Но переменная используется только один раз, вы также можете вставить ее в строку:

(print (cons n (triangle (- n 2))))

Наконец, у вас есть:

(defun triangle (n)
  (assert (oddp n))
  (if (< n 1)
      ()
      (print (cons n (triangle (- n 2))))))

Это вопрос стиля, но помните, что if, который возвращает nil в одной из его ветвей, обычно можно заменить на when или unless (здесь unless). Некоторым людям это не нравится, и они предпочитают не полагаться на возвращаемое значение nil when и unless. В любом случае, давайте проверим это:

(triangle 7)

Это дает:

(1)
(3 1)
(5 3 1)
(7 5 3 1)

Обратите внимание, что списки обратные. Один из способов решить проблему - заменить (print ...) на (print (reverse ...)), но это не сработает. Вы понимаете, почему?

Вместо этого давайте построим список в обратном направлении, что требует подсчета от 1 до достижения n:

(defun triangle (n &optional (c 1))
  (assert (oddp n))
  (when (<= c n)
    (print
      (cons c (triangle n (+ c 2))))))

Поскольку второй параметр является необязательным,мы можем назвать его как раньше:

(triangle 7)

Но теперь вывод:

(7)
(5 7)
(3 5 7)
(1 3 5 7)

Answer 2

Неверная скобка! Исходя из вашего отступа, я считаю, что вы хотите, чтобы следующее:

(if (< n 1) '())
    (setf ...

было бы if-then-else, где setf находится в ветви else. Чтобы это произошло, он должен выглядеть следующим образом:

(if (< n 1) '()
    (setf ...

В текущей настройке всегда оценивается setf.

Answer 3

Полезная стратегия состоит в том, чтобы отделить построение треугольника от его отображения. Таким образом, вы изменяете печатный формат без изменения кода для генерации треугольника.

Давайте выберем представление треугольника в виде списка списков, такого что create-triangle 7 => ((1) (1 3) (1 3 5) (1 3 5 7)). Следующая реализация генерирует желаемый треугольник:

(defun create-triangle (n)
  (labels ((aux (x acc)
             (if (> x n)
                 acc
                 (let* ((hd (car acc))
                        (new (append hd (list x))))
                   (aux (+ x 2) (cons new acc))))))
    (when (and (plusp n) (oddp n))
      (reverse (aux 1 nil)))))

Что следует отметить: Lisp является языком, ориентированным на выражения, поэтому часто возвращаемые операторы подобны не нужны.

Вспомогательная функция aux принимает целое число x и список acc. Если x больше n, он возвращает в соответствии с другим, мы создаем 2 локальные переменные: hd содержит первый список, найденный в нашем аккумуляторе: это будет самая последняя вычисленная строка. new формируется путем добавления текущего номера x к hd. Например, если acc = ((1 3 5) (1 3) (1)) и x = 7, то hd = (1 3 5) и new = (1 3 5 7) . Having made this computation, we call aux with the new x bound to x + 2 which is 7 in out example, and acc bound to ((1 3 5 7)) (1 3 5) (1 3) (1)) . This way we build the triangle in reverse. The function создать-треугольник , first checks that n is both positive and odd, and when that is satisfied, it returns the reverse of the triangle built by aux. Thus we get ((1) (1 3) (1 3 5) (1 3 5 7)) in our example. Ifn` не является положительным и нечетным, он просто возвращает пустой список. Вы измените это, чтобы выполнить проверку ошибок, как объяснил Coredump.

Теперь у нас есть треугольник, все, что осталось, это напечатать треугольник. Мы делаем это с помощью этой функции:

(defun print-triangle (xss)
  (when xss
    (format t "~&~{~a ~}" (car xss))
    (print-triangle (cdr xss))))

Интересная часть print-triangle - это выражение format. t указывает, что выводом является stdout, который обычно является экраном в управляющей строке;~& означает: убедитесь, что мы находимся на новой строке, а ~{~a ~} печатает содержимое списка с пробелом между ними, (car xss) является аргументом формата.

Теперь мы можем поместить обе функциивместе

(defun triangle (n)
  (print-triangle (create-triangle n)))

Быстрый тест:

CL-USER> (triangle 19)
1
1 3
1 3 5
1 3 5 7
1 3 5 7 9
1 3 5 7 9 11
1 3 5 7 9 11 13
1 3 5 7 9 11 13 15
1 3 5 7 9 11 13 15 17
1 3 5 7 9 11 13 15 17 19
NIL