Trying to print a triangle recursively in lisp. I get an overflow but I don’t know from where. Mind you I am new to Lisp programming.

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

(triangle 7)

It is always a good practice to break problems into smaller pieces, this approach makes also your code more modular, so you can change parts of your code more securely and flexible.

First you can define a small function to gather every row of your triangle as a list (and since you asked for a recursive solution, this is also recursively defined):

```
(defun upwards-range (x y &optional (by 2))
"Returns a list containing numbers from X to Y
by BY steps."
(if (>= x y)
(list y)
(cons x (upwards-range (+ x by) y by))))
(upwards-range 1 7) ; => (1 3 5 7)
```

Second create a function which gathers all the rows of your triangle. Please note that here i am implicitly expecting that the argument `N`

is an odd number. In the next function `show-triangle`

you could make assertions and return errors if not so.

```
(DEFUN TRIANGLE (N)
"COLLECTS TRIANGULAR LISTS."
(IF (= -1 N)
NIL
(APPEND (TRIANGLE (- N 2))
(LIST (UPWARDS-RANGE 1 N)))))
(TRIANGLE 7) ; => ((1) (1 3) (1 3 5) (1 3 5 7))
```

And the function for printing out the triangle:

```
(defun print-triangle (N)
"Makes sure that N is an odd number and prints the
rows of the triangle if so."
(assert (oddp N) (N) "~S is an even number. Please supply an odd onve" N)
(let ((rows (triangle N)))
(dolist (row rows)
(print row))))
(print-triangle 7)
```

returns:

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

A useful strategy is to separate building the triangle from displaying it.

This way, you change the printed format without changing the code to generate the triangle.

Let us choose to represent a triangle as a list of lists

such that `create-triangle 7 => ((1) (1 3) (1 3 5) (1 3 5 7))`

.

The following implementation generates the desired triangle:

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

Something to note: Lisp is an expression oriented language

so, often times, return like statements are not needed.

The auxiliary function `aux`

takes in an integer `x`

and

a list `acc`

. If `x`

is greater than `n`

, it returns acc

else, we create 2 local variables: `hd`

holds the first list

found in our accumulator: this will be the most recent row

computed. `new`

is formed by appending the current number `x`

to `hd`

. As an example, if `acc = ((1 3 5) (1 3) (1))`

and

`x = 7`

, then `hd = (1 3 5)`

and `new =`

(1 3 5 7)`.`

x

Having made this computation, we call aux with the new

x+2

bound to`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`

create-triangle

in reverse.

The function`, first checks that`

n`is both positive and odd,`

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

and when that is satisfied, it returns the reverse of the triangle

built by aux. Thus we get`in our example.`

n` is not positive and odd, it just returns the empty list.

If

You change this to do error checking as Coredump explained.

Now we have the triangle, all that is left is to print the triangle.

We do that with this function:

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

The interesting part of `print-triangle`

is the `format`

expression.

The `t`

indicates that the output is `stdout`

which is usually

the screen, in the control-string; `~&`

means: ensure we are on a new line, and

`~{~a ~}`

prints the contents of the list with a space between them,

`(car xss)`

is the format-argument.

Now we can put both functions together

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

A quick test:

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

Let’s review some parts of your code.

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

When you have an `if`

with only one branch, think about using `when`

or `unless`

, especially

if you put a `progn`

in the subform. For example, you can get rid of the `progn`

by switching

to a `when`

:

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

The `(when (not ...))`

expression is the same as `(unless ...)`

:

```
(unless (oddp n)
...)
```

Here, you print an error message, and return from the function.

Common Lisp has exceptions, which are made for those use cases.

You would typically call `(error "Not an odd integer: ~d" n)`

,

but here you can rely on the default behaviour of `assert`

, and

replace the whole check by:

```
(assert (oddp n))
```

If you try it with 2, you will obtain an error with a message similar to this:

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

Which is enough for tests.

Then, you have the following expression:

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

When you write `(list e1 e2 .. en)`

, it is as-if you wrote:

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

In your case, that means that `(list n)`

is the same as:

```
(cons n nil)
```

But since you then do the following:

```
(car (cons n nil))
```

You are just in fact allocating a cell and discarding it just to access `n`

.

The whole expression can be replaced by `n`

.

Third, you also uses `setf`

on `lst`

, where `lst`

is an undefined variable.

On most implementations (but really this behaviour is unspecified), that would set the global binding

for `lst`

, and it is a bad practice to set global variables from within functions.

You could use a `let`

instead:

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

But the variable is used only once, you may as well inline it:

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

Finally, you have:

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

This is a mattery of style, but remember that the `if`

that returns `nil`

in one of its branch can usually be replaced

by `when`

or `unless`

(here `unless`

). Some people don’t like that and prefer to not rely on the `nil`

return value of `when`

and `unless`

.

Anyway, let’s test it:

```
(triangle 7)
```

That gives:

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

Notice how the lists are backwards.

One way you could try to solve the problem is by replacing `(print ...)`

by `(print (reverse ...))`

, but that won’t work. Can you see why?

Instead, let’s build the list backwards, which requires to count up from 1, until we reach `n`

:

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

Since the second parameter is optional, we can call it as before:

```
(triangle 7)
```

But now, the output is:

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