From: David Nixon
Subject: recursion problems
Date: 
Message-ID: <77i85m$823$1@news8.svr.pol.co.uk>
.
I would like to ask you a Question about the following prog.

(defun wall (n)
  (cond ((= n 0) nil)
        (t (cons 'brick
                  (cons 'mortar (wall (- n 1)))))))

        (wall 5)

This prog is supposed to build a wall that must always start with brick.
(wall 3) should output > brick mortar brick, but instaed it outputs
>brick mortar brick mortar brick mortar
I think it is a recursive fault but I dont know how to fix ?
Thanks for your time
Dave

From: Gareth McCaughan
Subject: Re: recursion problems
Date: 
Message-ID: <86iueb1673.fsf@g.pet.cam.ac.uk>
David Nixon wrote:

> I would like to ask you a Question about the following prog.

You will probably get more helpful answers if you state openly
that this is homework...

> (defun wall (n)
>   (cond ((= n 0) nil)
>         (t (cons 'brick
>                   (cons 'mortar (wall (- n 1)))))))
> 
>         (wall 5)
> 
> This prog is supposed to build a wall that must always start with brick.
> (wall 3) should output > brick mortar brick, but instaed it outputs
> >brick mortar brick mortar brick mortar
> I think it is a recursive fault but I dont know how to fix ?

The skill you need to develop is thinking through what a
program does as it runs. I suspect it's impossible to be
a competent programmer in any language without that skill.
(Some languages require slightly different versions of it.)

So, let's think about what happens when you say (wall 3).

The first clause of the COND requires (= n 0). n isn't 0 here,
so try the next clause. That requires T, so this clause gets
selected. So the result of (wall 3) is the result of
  (cons 'brick (cons 'mortar (wall (- n 1))))
where n is 3.

In other words, it's the list (brick mortar ...), where
(...) is the result of (wall 2).

Similarly, the result of (wall 2) is (brick mortar ...) where
(...) is the result of (wall 1).

So far, we've seen that (wall 3) produces (brick mortar brick mortar ...)
where (...) is the result of (wall 1). I'll leave the rest to you; you
should already have worked out what the problem is. Fixing it is pretty
easy.

Unless, of course, you want (wall 4) to produce something sensible;
in that case, you need to rethink the design a little.

-- 
Gareth McCaughan       Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk  Cambridge University, England.
From: Ian Wild
Subject: Re: recursion problems
Date: 
Message-ID: <369CBDF3.E72EE8B8@cfmu.eurocontrol.be>
David Nixon wrote:

> (defun wall (n)
>   (cond ((= n 0) nil)
>         (t (cons 'brick
>                   (cons 'mortar (wall (- n 1)))))))
> 
>         (wall 5)
> 
> This prog is supposed to build a wall that must always start with brick.

which it does


> (wall 3) should output > brick mortar brick, but instaed it outputs
> >brick mortar brick mortar brick mortar

> I think it is a recursive fault but I dont know how to fix ?

There's only one place that inserts 'brick, and that
also inserts 'mortar.  You're always going to get
them in pairs, recursion or no, until this changes.

Hint: how tall is a very short wall?