Lisp : how to use recursion to defun a function that given a nonnegative integer N, produce the list of all integers from 1 up to and including N?

write a function in lisp called number(N) that you have to use a nonnegative integer N, and produce the list of all integers from 1 up to and including N.

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

I checked some questions, but most of them use loop and range, but this question doesn't allowed me to do this, so I have to use recursion instead:

here is my code, but this code keeps giving me warning:

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

I think my algorithm is correct ,but because I am new to lisp, I still don't know how to write the function properly. It is grateful if anyone could gave me any help.

Solution

The way to think about this is to think about what the algorithm should be:

To compute the numbers from 1 to n:

if n is less than 1 then there are no numbers, so this is the empty list;

otherwise we want a list which looks like (... n), where ... is all the numbers from 1 to n-1.

Note that we want the numbers in forward order: this is going to be critical.

Doing this is slightly difficult in Lisp because we want the number to be at the end of the list, and access to the ends of lists is hard.

Here is the start of a version which builds the list backwards (so this is not the right answer).

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

Well, OK, what function should we call recursively? Do we have a function which returns the list we want? Well, yes: it's numbers, with an argument which is one less than n!

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

And this function works. But it gets the wrong answer: the list is backwards:

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

There are two fixes to this problem: the first is to build the list forwards, using append. This version looks like this (remember append wants to append two lists: it doesn't append an element to the end of a list):

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

This gets the right answer:

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

but it's a terrible answer: append has to walk all the way down the list (lists in Lisp are chains of conses: there is no fast access to the end of a list), copying it as it goes, to append the new element. So this has absolutely terrible space & time complexity. Programs written like this are why 'Lisp is slow'.

A better approach is to build the list backwards and then reverse it.

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

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

The problem with this, from the homework perspective, might be that using reverse is not allowed. That's OK, we can write it, recursively. The implementation is slightly fiddly, but this is going to help us below.

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

The way this works is that reverse-list calls this auxiliary function with an extra argument. The auxiliary function then checks the list, and if it's not empty it calls itself with the tail of the list and the head of the list consed onto the auxiliary argument. If it is empty, it returns the auxiliary argument. It's a little subtle but you can see that this in fact reverses the list.

So now we can write our function using only recursive functions we wrote:

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

But now there should be a moment of inspiration: why are we doing this whole build-it-backwards-and-reverse-it thing? Why don't we just make numbers do the accumulator trick itself! Well, we can do that:

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

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

And now we don't need to reverse the list, and for added value our function is 'tail recursive' and will generally be compiled much more efficiently.

A real-life version of numbers might look more like this, using a local function:

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

Here is a comparison between the version of numbers using append and the above function, on an argument small enough that the append version does not overflow the stack.

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

You can see how terrible the append version is, and how good the other one is: this is a 64-bit Lisp, and conses are two words or 16 bytes: it has allocated precisely 2000 cons cells which is the minimum it could do.