Лисп: как использовать рекурсию для определения функции, для которой задано неотрицательное целое число N, получить список всех целых чисел от 1 до N включительно?

Question

напишите в lisp функцию с именем number (N), чтобы вам приходилось использовать неотрицательное целое число N, и создавайте список всех целых чисел от 1 до N включительно.

(defun numbers (N)  
  (if (<= N 0)
      nil
      (cons N nil)
      (numbers (- N 1)))

Я проверил нескольковопросы, но большинство из них используют цикл и диапазон, но этот вопрос не позволил мне сделать это, поэтому я должен использовать рекурсию вместо этого:

вот мой код, но этот код продолжает давать мне предупреждение:

; caught STYLE-WARNING:
;   The variable N is defined but never used.
; 
; compilation unit finished
;   caught 1 ERROR condition
;   caught 1 STYLE-WARNING condition

Я думаю, что мой алгоритм правильный, но, поскольку я новичок в lisp, я все еще не знаю, как правильно написать функцию.Буду признателен, если кто-нибудь сможет мне помочь.

Answer 1

Способ думать об этом - подумать о том, каким должен быть алгоритм:

Для вычисления чисел от 1 до n:

• если n меньше 1, то чисел нет, поэтому это пустой список;
• в противном случае нам нужен список, который выглядит как (... n), где ... - это все числа из1 до n-1.

Обратите внимание, что мы хотим, чтобы числа были в прямом порядке: это будет критично.

В Лиспе сделать это немного сложнопотому что мы хотим, чтобы номер был в конце списка, а доступ к концам списков затруднен.

Вот начало версии, которая строит список в обратном направлении (поэтомуэто неправильный ответ).

(defun numbers (n)
  (if (< n 1)
      '()                               ;the empty list
    ;; n 1 or more, so build a list which is (n . ...)
    (cons n <some function involving n>)))

Хорошо, хорошо, какую функцию мы должны вызывать рекурсивно?У нас есть функция, которая возвращает список, который мы хотим?Ну, да: это numbers, с аргументом, который на единицу меньше n!

(defun numbers (n)
  (if (< n 1)
      '()
    (cons n (numbers (- n 1)))))

И эта функция работает.Но он получает неправильный ответ: список задом наперед:

> (numbers 10)
(10 9 8 7 6 5 4 3 2 1)

Существует два исправления этой проблемы: первое - построить список вперед, используя append.Эта версия выглядит следующим образом (помните, append хочет добавить два списка: он не добавляет элемент в конец списка):

(defun numbers (n)
  (if (< n 1)
      '()
    (append (numbers (- n 1)) (list n))))

Это дает правильный ответ:

> (numbers 10)
(1 2 3 4 5 6 7 8 9 10)

но это ужасный ответ: append должен пройти весь список вниз (списки в Лиспе - это цепочки понятий: нет быстрого доступа к концу списка), копируя его, как он идет, чтобы добавить новый элемент.Так что это имеет абсолютно ужасную пространственно-временную сложность.Программы, написанные следующим образом, объясняют, почему «Lisp работает медленно».

Лучшим подходом является построение списка в обратном направлении, а затем наоборот.

(defun numbers (n)
  (reverse (numbers-backwards n)))

(defun numbers-backwards (n)
  (if (< n 1)
      '()
    (cons n (numbers-backwards (- n 1)))))

Проблема с этим, с точки зрения домашней работыВозможно, использование reverse не разрешено.Это нормально, мы можем написать это рекурсивно.Реализация немного сложная, но это поможет нам ниже.

(defun reverse-list (l)
  ;; in real life reverse-list-accumulator would be a local function
  (reverse-list-accumulator l '()))

(defun reverse-list-accumulator (l accum)
  (if (null l)
      accum
    (reverse-list-accumulator (rest l) (cons (first l) accum))))

Способ, которым это работает, заключается в том, что reverse-list вызывает эту вспомогательную функцию с дополнительным аргументом.Вспомогательная функция затем проверяет список, и если он не пустой, она вызывает себя с хвостом списка и заголовком списка, сконцентрированным на вспомогательном аргументе.Если он пуст, он возвращает вспомогательный аргумент.Это немного незаметно, но вы можете видеть, что это фактически переворачивает список.

Так что теперь мы можем написать нашу функцию, используя только рекурсивные функции, которые мы написали:

(defun numbers (n)
  (reverse-list (numbers-backwards n)))

Но теперь должно бытьмомент вдохновения: почему мы делаем всю эту работу «1065»?Почему бы нам просто не заставить numbers сделать трюк с самим аккумулятором!Что ж, мы можем сделать это:

(defun numbers (n)
  (numbers-accumulator n '()))

(defun numbers-accumulator (n accum)
  (if (< n 1)
      accum
    (numbers-accumulator (- n 1) (cons n accum))))

И теперь нам не нужно переворачивать список, и для добавленной стоимости наша функция 'tail recursive' и, как правило, будет компилироваться намного эффективнее.

---

Реальная версия numbers может выглядеть более похоже на это при использовании локальной функции:

(defun numbers (n)
  (labels ((numbers-accumulator (m accum)
             (if (< m 1)
                 accum
               (numbers-accumulator (- m 1) (cons m accum)))))
    (numbers-accumulator n '())))

Вот сравнение версии numbers с использованием append и вышеупомянутая функция на аргументе, достаточно маленьком, чтобы версия append не переполняла стек.

> (time (progn (numbers/append 2000) (values)))
Timing the evaluation of (progn (numbers/append 2000) (values))

User time    =        0.024
System time  =        0.001
Elapsed time =        0.017
Allocation   = 32176304 bytes
97 Page faults

> (time (progn (numbers 2000) (values)))
Timing the evaluation of (progn (numbers 2000) (values))

User time    =        0.000
System time  =        0.000
Elapsed time =        0.001
Allocation   = 32000 bytes
0 Page faults  

Вы можете видеть, насколько ужасна версия append и насколько хороша другая.is: это 64-битный Lisp, и conses - это два слова или 16 байтов: он выделил ровно 2000 cons-ячеек, что является минимальным значением, которое он может сделать.

Answer 2

IF, как правило, имеет общий синтаксис, но есть исключения

Обычно в Лиспах, таких как Common Lisp, оператор if допускает следующий синтаксис:

IF test-form then-form [else-form]

Это означает, что в Лиспе обычно допускается ноль или одна else-форма . Примером является if в Common Lisp.

В Emacs Lisp допускается несколько else-форм . Emacs Lisp имеет следующий синтаксис:

IF test-form then-form else-form* 

Это означает, что в Emacs Lisp допускается ноль или более else-форм .

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

Ваш код

a) Предположим, что вы используете Common Lisp с его синтаксисом IF .

Ваш код:

(defun numbers (N)  
  (if (<= N 0)
      nil
    (cons N nil)
    (numbers (- N 1)))

В вашем коде проблема в том, что существует более одного предложения. Вам нужно написать версию, в которой есть еще одно предложение.

b) Предположим, что вы используете Emacs Lisp с его синтаксисом IF с несколькими другими формами.

Ваш код:

(defun numbers (N)  
  (if (<= N 0)
      nil
    (cons N nil)
    (numbers (- N 1)))

Здесь форма (cons N nil) разрешена, но не имеет никакого эффекта. Его возвращаемое значение не используется и не имеет побочных эффектов. Вы можете удалить его, и это не будет иметь никакого значения. Опять же: вам нужно, как совместить его эффект с формой (numbers (- N 1)).

Синтаксическая ошибка: отсутствует закрывающая скобка

В вашем коде есть другая проблема. S-выражения не завершены -> закрывающая скобка отсутствует:

(defun numbers (N)  
  (if (<= N 0)
      nil
      (cons N nil)
      (numbers (- N 1)))

Как видите, закрывающая скобка в конце отсутствует.

Таким образом, ваш код не может быть прочитан Lisp.

Существует два способа избежать этой проблемы:

• посчитать скобки и установить их соответственно
• используйте редактор для подсчета скобок

Большинство людей предпочитают последнее.