Re: Eight Queens problem (was Re: Kindness)

[Robert Dewar <robert_dewar@my-deja.com>]

In article <7r50tj$sp3$1@nnrp1.deja.com>,
  bourguet@my-deja.com wrote:
> function fact(n : natural) return natural is
> begin
>    if n = 0 then
>       return 1;
>    else
>       return n*fact(n-1);
>    end if;
> end fact;
>
> tail recursive? There is a multiplication to be executed after
> the return.

You are right, it is not tail recursive as normally expressed,
however the transformation here to a tail recursive version is
a standard one (and one that is for example performed by many
compilers).

The real point is that you want to choose something which shows
that recursion is useful, not merely a neat way of writing a
simple loop in a kludgy manner, which will be quite inefficient
if the compiler does NOT do pretty clever tail recursion
elimination. I would not expect ANY Ada compiler to be that
clever, and in fact, it would not surprise me to find that
many Ada compilers do no tail recursion elimination at all.

P.S. It is interesting how important this optimization can be.
The Realia COBOL compiler does extensive tail recursion
elimination (on the x86, in its simplest form, this consists
of replacing a CALL x/RET sequence by JMP X), and it turned
out to be a VERY important optimization. That sounds very
strange, given that COBOL does not allow recursion, but of
course general tail recursion elimination also catches the
case of calling some *other* procedure as the last step.


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.